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.

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.

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 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 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?

• I think $m < n$ condition makes this problem quite hard. Nov 16 '19 at 6:58
• 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$ Nov 16 '19 at 16:01
• 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. 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)

then there exists $$1\leq m 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

Now, note that if $$1\leq m and $$mn+1$$ is not prime, then some prime $$p 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 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)

$$j\left(\prod_{p\in A}p\right)-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.