Stack Exchange Network

Stack Exchange network consists of 174 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [prime-numbers]

Questions where prime numbers play a key-role, such as: questions on the distribution of prime numbers (twin primes, gaps between primes, Hardy–Littlewood conjectures, etc); questions on prime numbers with special properties (Wieferich prime, Wolstenholme prime, etc.). This tag is often used as a ...

0
votes
0answers
76 views

Dirichlet theorem on primes in ap with a prime index

Someone know a result like this: Given $a,b\in\mathbb{N}$, with $a>b>0$ and $(a,b)=1$,then there exist at least one prime $p$ such that $ap+b$ is a prime number too.
0
votes
0answers
117 views

The prime number matrix sieve [on hold]

I have derived the following theorem: An odd positive integer $N=6n−1$ is a prime iff neither of two diophantine equations $6x^2+(6x−1)y=n$ $6x^2+(6x+1)y=n$ has a solution. An odd positive ...
5
votes
1answer
599 views

Is there a 2-power-twinless prime?

Call two primes 2-power-twins if their difference is (can you guess?) a power of 2. For example, 11 and 19 are 2-power-twins. Is there a 2-power-twinless prime? I would imagine that this is doable ...
9
votes
0answers
177 views

On the permanent $\text{per}[i^{j-1}]_{1\le i,j\le p-1}$ modulo $p^2$

Let $p$ be an odd prime. It is well-known that $$\det[i^{j-1}]_{1\le i,j\le p-1}=\prod_{1\le i<j\le p-1}(j-i)\not\equiv0\pmod p.$$ I'm curious about the behavior of the permanent $\text{per}[i^{j-...
2
votes
2answers
257 views

On the sum $\sum_{\pi\in S_{n}}e^{2\pi i\sum_{k=1}^{n}k\pi(k)/n}$

Motivated by Question 316142 of mine, I consider the new sum $$S(n):=\sum_{\pi\in S_{n}}e^{2\pi i\sum_{k=1}^{n}k\pi(k)/n}$$ for any positive integer $n$, where $S_n$ is the symmetric group of all the ...
31
votes
1answer
3k views

Does the algorithm of the Greeks produce all prime numbers?

Let ${\cal P}$ be the set of prime numbers. Define a subset ${\cal P}'=\{p_1,p_2,p_3,\cdots\}$ of ${\cal P}$ by setting $p_1=2$ and defining $p_{n+1}$ to be the smallest element of ${\cal P}$ ...
6
votes
2answers
261 views

Reference Request for a result on divisors of $p-1$

I have seen this result in several places without an English reference: There exist infinitely many primes $p$ such that $p-1=2q_1q_2$ where $q_1$ and $q_2$ are prime numbers with $q_1,q_2>p^{1/4}$...
2
votes
1answer
207 views

Extension of Dirichlet's Arithmetic Progression Theorem

Dirichlet's Arithmetic Progression Theorem states that: Given $a, b\in\mathbb{Z^+}$ with $(a,b)=1$, then $a+kb$ is prime for an infinite number of $k\in\mathbb{Z^+}.$ For any given $a$ and $b$ let ...
20
votes
0answers
270 views

Can we write each positive rational number as $\frac1{p_1-1}+\ldots+\frac1{p_k-1}$ with $p_1,\ldots,p_k$ distinct primes?

It is well-known that any positive rational number can be written as the sum of finitely many distinct unit fractions. This is easy since $$\frac1n=\frac1{n+1}+\frac1{n(n+1)}\quad\text{for all}\ n=1,2,...
0
votes
0answers
121 views

On segments of the series $\sum_p\frac1{p-1}$

Here I ask a question concerning segments of the divergent series $$\sum_p\frac1{p-1}=\sum_{k=1}^\infty\frac1{p_k-1},\tag{$*$}$$ where $p$ runs over all the primes, and $p_k$ denotes the $k$-th prime. ...
1
vote
0answers
88 views

Sum of a prime and a number one can write as a sum of 2 squares in exactly $ k $ ways

Following this interesting question : Sieve bound for the sum of two squares I define $ P_{k}(n)=1 $ if and only if $ n $ is the sum of an odd prime and an integer that can be written in exactly $ ...
3
votes
0answers
163 views

Can we write each positive integer as $x^2+y^2+\varphi(z^2)$?

As odd squares are congruent to $1$ modulo $8$, any integer of the form $4^k(8m+7)$ with $k,m\in\mathbb N=\{0,1,2,\ldots\}$ cannot be written as the sum of three squares. To avoid such congruence ...
0
votes
0answers
61 views

Relation between primeness, coprimeness, totient, and gcd function

There are two number theoretic facts that seem to be unrelated at very first sight but at second sight seem to be strongly related to each other: (1) Primeness of one number and coprimeness of two ...
1
vote
0answers
77 views

Probability distribution from equidistribution - II

Pick a random pair $(a,b)\in\mathbb Z_n^2\backslash\{0,0\}$ and denote $N(a,b)$ to be minimum $\ell_2$ norm of vector $(x,y)$ as $(x,y)$ ranges over all non-zero integral solutions to $(x,y)\equiv t(a,...
7
votes
0answers
231 views

Proving infinitely many primes using algebraic geometry ideas

There are at least two well known proofs of the infinitude of primes (Euclid's original one and Euler's proof using L-series) and both of them can be extended to prove more general statements of the ...
-1
votes
0answers
67 views

An asymptotics for $ r_{0}(n) $ through Euler totient

Assuming Goldbach's conjecture, let's denote by $ r_{0}(n) $ the smallest positive integer $r $ such that both $ n-r $ and $ n+r $ are prime, provided $ n $ is a large enough positive composite ...
7
votes
1answer
372 views

Linear equations in primes

Quoting from Green-Tao, "Linear equations in primes" (especially Cor. 1.9 in https://arxiv.org/pdf/math/0606088.pdf), any system of linear forms of finite complexity and without any local obstructions ...
0
votes
0answers
99 views

Reference request for bounds of $n$-th composite

Motivation I will briefly elaborate here my motivations for asking the question. If you are not interested in it then please go to the questions. Recently during trying to understand and prove the ...
1
vote
3answers
565 views

Question concerning twin primes

The multiplication graphs $p/q$ – with an edge between $a,b$ iff $ap \equiv b\operatorname{mod} q$ – for some twin primes $p$ and $q = p+2$ reveal an astonishing pattern: $(p+0)/(p+1)$ ...
2
votes
1answer
160 views

Does $\det[\lfloor(i^2+j^2)/p\rfloor]_{1\le i,j\le(p-1)/2}$ vanish for each prime $p>7$ with $p\equiv3\pmod4$?

Let $\lfloor x\rfloor$ be the floor function. QUESTION: Does the determinant $$D_p=\det\left[\left\lfloor\frac{i^2+j^2}p\right\rfloor\right]_{1\le i,j\le(p-1)/2}$$ vanish for each prime $p>7$ with ...
2
votes
0answers
99 views

Chen primes and permutations

In 1973 the Chinese mathematician J.-R. Chen proved that there are infinitely many primes $p$ such that $p+2$ is a product of at most two primes. Nowadays such primes $p$ are called Chen primes. For $...
1
vote
0answers
82 views

Roots of unity, vanishing sums and derivatives

Fix integers $n\geqslant1$ and $k\geqslant 0$. For an integer $i$, the $k$-fold derivative of $x^i$ can be denoted by $i^{\underline{k}}x^{i-k}$ where $i^{\underline{k}}$ means $i(i-1)\cdots(i-k+1)$ ...
0
votes
0answers
112 views

Permutations $\pi\in S_n$ with $p_k+p_{\pi(k)}+1$ prime for all $k=1,\ldots,n$

As usual, let $S_n$ be the symmetric group of all permutations of $\{1,\ldots,n\}$. QUESTION: Is my following conjecture true? Conjecture. For any positive integer $n$, there is a permutation $\pi\...
2
votes
2answers
684 views

If Goldbach's Conjecture is eventually true, is it necessarily true?

We have all heard that if Goldbach's conjecture is independent, then it is true. This is because if GC is false then there is an even number which is not the sum of two primes, and hence a finite ...
17
votes
1answer
2k views

A mysterious connection between primes and squares

Motivated by two previous questions of mine (cf. Primes arising from permutations and Primes arising from permutations (II)), here I ask a curious question which connects primes with squares. ...
3
votes
0answers
258 views

Primes arising from permutations (II)

In Question 315259 (cf. Primes arising from permutations) I asked a question on primes arising from permutations which looks quite challenging. Here I pose a new question in this direction which does ...
8
votes
1answer
413 views

Primes arising from permutations

Recently, Paul Bradley proved in arXiv:1809.01012 that for any positive integer $n$ there is a permutation $\pi_n$ of $\{1,\ldots,n\}$ such that $k+\pi_n(k)$ is prime for every $k=1,\ldots,n$ (cf. ...
1
vote
0answers
121 views

Prime generating polynomials

Continuation to this previous question. According to Lemke-Oliver, an irreducible polynomial $G$ of degree $g$ with positive leading coefficient and $\Gamma_G\neq0$ (with $\Gamma_G$ a certain factor ...
9
votes
0answers
161 views

Semi-primes represented by quadratic polynomials

According to Lemke-Oliver, irreducible quadratic polynomials $G$ with positive leading coefficient and $\rho(2)<2$, (where $\rho(m)$ denotes the number of incongruent solutions to the congruence $G(...
2
votes
1answer
149 views

On the function $f_m(p)=\left|\left\{1\leqslant k<\frac p2:\ \left\{\frac{k^m}p\right\}>\frac12\right\}\right|$

Let $m>1$ be an integer and let $p$ be an odd prime. Can we say something nontrivial about $$f_m(p):=\left|\left\{1\leqslant k<\frac p2:\ \left\{\frac{k^m}p\right\}>\frac12\right\}\right|$$ (...
8
votes
0answers
149 views

Integers with fixed number of prime factors in arithmetic progression

Famously, there are arbitrarily long arithmetic progressions $x$, $x+y$, ..., $x+ky$ consisting of primes, by Green-Tao. I was wondering whether the following generalization is also known (by the same ...
4
votes
1answer
209 views

Quadratic Nonresidue

Suppose $r$ integers $n_1, \ldots, n_r$ are given such that $0<|n_i|<N$ for $1 \leq i \leq r$ and for a natural number $N.$ Is it possible to find a prime number $p$ such that all numbers $n_1, \...
10
votes
1answer
234 views

A set of prime numbers

Consider a non-empty set $S$ of primes, with the property that, for every finite subset $S'\subset S$, all the primes dividing $\left(\prod_{k\in S'}k\right)+1$ are in $S$. For instance, it can ...
-1
votes
2answers
329 views

Conjecture: $ x\leqslant f(x)\leqslant x+x^{\log_{113}13} \{x|1\leqslant x\leqslant+\infty,x\in \mathrm{positive~integer}\}$?

Function f(x) is the most closest prime number not less than $x$. $f(5)=5\qquad f(9)=11$ Conjecture: $ x\leqslant f(x)\leqslant x+x^{\log_{113}13} \{x|1\leqslant x\leqslant+\infty,x\in \mathrm{...
2
votes
1answer
157 views

The largest number $y$ such that $(x!)^{x+y}|(x^2)!$

Since the multiplication of $n$ consecutive integers is divided by $n!$, then $(n!)^n|(n^2)!$ with $n$ is a positive integer. Are there any formula of the function $y=f(x)$ that shows the largest ...
8
votes
1answer
174 views

For which primes does this iterated function act transitively? (Sort of a finite analogue of Collatz conjecture.)

Background: I was trying to prove something having to do with cyclic group actions on matroids and was able to show that what I want holds if a particular elementary-looking number-theoretic property ...
1
vote
1answer
607 views

Is every prime greater than 5, less than the sum of the two previous primes?

Can one prove by elementary means (such as Paul Erdös' proof of Bertrand's Postulate) that every prime greater than 5 is less than the sum of the two primes immediately preceding it?
5
votes
1answer
379 views

Is the following weak version of second Hardy-Littlewood conjecture already known?

Very recently I was going through my previous MSE posts and I stumbled upon some of them regarding the Second Hardy-Littlewood Conjecture which states that, For all $x,y\ge 2$ we have, $$\pi(x)+\...
5
votes
1answer
319 views

consecutive prime gaps and explicit bound

I am aware of the theorem that $p_{n+1}- p_n \leq n^{0.525}$ which is true for all sufficiently large numbers due to Baker, but if i want to make the implicit "for all sufficiently large numbers" ...
6
votes
1answer
214 views

Prime plus square equals prime

Furstenberg–Sárközy's theorem states that if a set of positive integers has positive upper density, then there exists (infinitely many) pair of elements of the set, whose difference is a perfect ...
6
votes
0answers
109 views

Does the primality of the number of dimensions affect its properties?

Motivated by How does the parity of a dimension affect its properties? I dare to ask the following question (with thanks to my colleague Vedran Dunjko): We happen to live in a world of prime ...
1
vote
1answer
79 views

How many iterations the best biprime factoring method has to factor a number [closed]

I'm researching method of biprime number factoring. I have a biprime number 1012322327 * 1115382761 (19 decimal digits= 1129126872111204847). I'd like to know how many iterations (or trials) the best ...
12
votes
3answers
747 views

Stronger versions of Wilson's Theorem

Problem Let $c \in \mathbb{N}$ $;$ $\exists$ a prime $p$ for which: $$p^c \mid (p-1)!+1$$ Does $\exists$ $M$ $\in$ $\mathbb{N}$ $;$ $\forall$ $c \geqslant M$ $;$ $\nexists$ $p$ ...
0
votes
0answers
415 views

Conjectured primality tests for specific classes of $k\cdot b^n \pm 1$

Can you provide proofs or counterexamples for the claims given below? Inspired by Lucas-Lehmer-Riesel primality test I have formulated the following two claims: First claim Let $P_m(x)=2^{-m}\...
3
votes
1answer
161 views

Almost-Primes in Short Intervals

Let $S$ be the set of integers which are a product of $k$ distinct primes, $k$ a fixed positive integer (the condition that the primes are distinct is not crucial). Landau used the Prime Number ...
2
votes
0answers
191 views

What is the sum of the binomial coefficients ${n\choose p}$ over prime numbers?

What is known about the asymptotics, lower and upper bound of the sum of the binomial coefficients $$ S_n = {n\choose 2} + {n\choose 3} + {n\choose 5} + \cdots + {n\choose p} $$ where the sum runs ...
1
vote
1answer
345 views

Primality test for generalized Fermat numbers

This question is successor of Primality test for specific class of generalized Fermat numbers . Can you provide a proof or a counterexample for the claim given below? Inspired by Lucas–Lehmer–Riesel ...
8
votes
1answer
281 views

Riemann sum formula for definite integral using prime numbers

I had asked this question in MSE. It got lot of upvotes but no answer (except one which was too long to be posted as a comment) hence I am posting it in MO. While answering another question in MSE I ...
0
votes
0answers
106 views

What is known about the lower bound for the integers $n$ for which $n$ minus the first $k$ odd primes are $k$ composite numbers?

Question edited in view of the comments below By Yamada's paper we can conclude that if $n>e^{e^{36}}$ be an even number then it can always be written as the sum of a prime and a semi-prime. My ...
0
votes
0answers
52 views

Distribution of witnesses that yields a factorization of $n$

For each natural odd number $n$, let $A_n$ be the set of all $1 < a < n$ for which $n$ is a pseudoprime to base $a$ but not a strong pseudoprime to base $a$. This is the set of bases for which ...