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.

Question

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?

Answer 1

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.

Answer 2

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

$$S_p=\{k_p,k_p+p,k_p+2p,\cdots,h_p\}$$

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.