I was using Python to explore some interesting lexicographically earliest sequences. I was looking into the sequence of numbers such that $a(1)=1$ and $a(n)$ is the smallest number such that $a(k)n+1$ is not prime for any $k<n$.

After computing this sequence, it appeared to be exactly the odd integers. The absence of even integers interested me, as that suggested that for every even integer $n$ there exists an odd $m<n$ such that $mn+1$ is prime. After checking with Mathematica, this appeared to be true. In fact, this suggested the more general conjecture in the title:

For all $n\in\mathbb{N}$ with $n>1$ there exists an $m\in\mathbb{N}$ with $m<n$ such that $mn+1$ is prime.

This doesn't sound too difficult, but then again there are plenty of nice-sounding prime conjectures that remain unsolved, so this could be one of those.

How could this be proven? And if its unsolved / really difficult, what is the name of the conjecture?

  • 1
    $\begingroup$ I think $m < n$ condition makes this problem quite hard. $\endgroup$ Nov 16 '19 at 6:58
  • $\begingroup$ Letting $m=n-a$, can be restated as $\forall n>1,\ \exists 1\le a <n$ such that $n^2-na+1 \in \mathbb P$ $\endgroup$ Nov 16 '19 at 16:01
  • $\begingroup$ Note that for numbers in the range $[n + 1, n^2 + 1)$, the "probability" of being prime is about $\frac{1}{2\log n}$ to $\frac{1}{\log n}$. So it's "almost certain" that among $n$ of them there is a prime. This heuristic argument should convince you that the truth of this conjecture is not surprising. Of course, as many other such conjectures, a rigorous proof is perhaps out of reach from today's technology. $\endgroup$
    – WhatsUp
    Nov 17 '19 at 23:56

See https://en.wikipedia.org/wiki/Linnik%27s_theorem for some bounds on $a(n)$. It is not exactly what you want but at least it's a start.


Here is a sufficient condition for the conjecture to be true: If

$$j\left(\frac{\prod_{p\leq n}p}{\text{rad}(n)}\right)<n$$

then there exists $1\leq m<n$ such that $mn+1$ is prime. Here, $j(n)$ is the Jacobsthal Function, $\text{rad}(n)$ is the Radical of $n$, and the product is over all primes less than or equal to $n$. Note that this is not a necessary condition as it does not hold for $13, 17, 19, 23, 25$, or $29$ (it does not seem to hold for powers of primes) but these are not counterexamples to your conjecture.

Now, assume the condition above holds for some $n$. Define $A$ as the set of all primes less than $n$ which also do not divide $n$. Note that

$$\prod_{p\in A}p=\frac{\prod_{p\leq n}p}{\text{rad}(n)}.$$

This is because $\prod_{p\leq n}p$ is all primes less than or equal to $n$, while $\text{rad}(n)$ divides out the prime factors of $n$. If $n$ is primes, then clearly

$$\frac{\prod_{p\leq n}p}{\text{rad}(n)}=\frac{\prod_{p\leq n}p}{n}=\prod_{p<n}p=\prod_{p\in A}p.$$

Now, note that if $1\leq m<n$ and $mn+1$ is not prime, then some prime $p<n$ divides $mn+1$. If this was not the case, then

$$mn+1=p_1^{k_1}p_2^{k_2}\cdots p_l^{k_l}\geq p_1p_2\geq n^2>n^2-n+1=(n-1)n+1\geq mn+1$$

which is impossible. Now, if $p|mn+1$ and $p|n$, then

$$0\equiv mn+1\equiv 1(\text{mod }p)$$

which is also absurd. Thus, if $mn+1$ is not prime, then it has a prime factor in $A$. Of course, the reverse is also true: if $mn+1$ has a prime factor in $A$, then $mn+1$ is not prime. Thus, $mn+1$ is prime if and only if it has no prime factors in $A$.

We shall now show that the condition presented above implies the existence of $1\leq m<n$ such that $mn+1$ has no prime factors in $A$. First, note that for any $k\in\mathbb{Z}$ and any $p\in A$, if $p|kn+1$ then

$$p|(k+a)n+1\iff p|a.$$

For $p\in A$, define $k_p$ as the smallest natural such that $p|k_pn+1$ and define $h_p$ as the largest natural less than $n$ such that $p|h_pn+1$. Additionally, for all $p\in A$, define


which is the set of all integers such that if $m\in S_p$, then $p|mn+1$. Thus, in order to show that $mn+1$ has no prime factors in $A$, it suffices to show

$$m\not\in\bigcup_{p\in A}S_p$$

Note that

$$\bigcup_{p\in A}S_p\subseteq \{1,2,\cdots n-1\}.$$

which has $n-1$ elements in it.

Returning to the Jacobsthal function, $j(n)$ is the maximal gap in a list of all the integers relatively prime to $n$. That is, the length of a run of integers such that no integers are relatively prime to $n$ is $j(n)-1$. Now, if the condition presented at the beginning holds, we have

$$j\left(\prod_{p\in A}p\right)<n$$

$$j\left(\prod_{p\in A}p\right)-1<n-1$$

which implies that the longest run of integers which are not relatively prime to $\prod_{p\in A}p$ is less than $n-1$. However, there are $n-1$ elements of $\{1,2,\cdots n-1\}$, which implies that at least one of these elements is relatively prime to $\prod_{p\in A}p$. Thus, this integer is relatively prime to all $p\in A$, which proves the conjecture.

The reason this is a sufficient, but not necessary condition is that $j(n)$ describes the longest run of which are not relatively prime to $\prod_{p\in A}p$ in all the integers. However, the conjecture above only considers integers less than $n$. Since it is generally the case that

$$\prod_{p\in A}p>n$$

this approach only provides an upper bound. Someone more familiar than myself might be able to turn this condition into a condition on $n$. However, I haven't found anything like that yet.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.