# The difference of two coprime composites

I guess this is a simple task for them who know some number theory:

Any natural number is the difference between two coprime composites.

Tested up to 1000.

I develop some computer tools to investigate sets and now and then find some patterns or connections that makes me formulate a conjecture, which in my mind just is a word for an unproved statement.

• The odd case is easy - Suppose $n$ is odd, and $p, q$ are odd primes which are not factors of $n$, then $n=(n+pq)-pq$ where the first summand is composite because it is even. Commented Dec 25, 2017 at 12:41
• Since the set of primes $\mathcal{P}$ has density $0$, the claim is obvious. For any $n\in\mathbb{N}^+$ $$E_n=\left[(\mathbb{N}_{\geq 2}\setminus\mathcal{P})+n\right]\cap (\mathbb{N}_{\geq 2}\setminus\mathcal{P})$$ is non-empty since it has a positive density. Assuming that the density of $E_n$ is zero we have that at most half of the elements of $a,a+n,a+2n,a+3n,\ldots$ are composite for any $a\in\mathbb{N}^+$, hence the density of composite numbers is bounded by $\frac{1}{2}$, contradiction. Then the coprimality constraint does not affect this topological argument by much. Commented Dec 25, 2017 at 14:48

If $n$ is a positive integer then $(2n + 1)! + n + 1$ and $(2n + 1)! + 2n + 1$ are coprime and composite.

ElieLuis from a comment:

Clearly the first number is divisible by $n+1$ and the second one is divisible by $2n+1$. Also, assuming any number (different from $1$) divides both of them, it must also divide $n$ which is their difference. But if it divides $n$, then it cannot divide $(2n+1)!+n+1$, since both $(2n+1)!$ and $n$ are divisible by our divisor.

(Added by Lehs who wishes he could do such clear thinking and produce better context to his questions).

• Can you elaborate on why the two numbers are coprime and composite? It would make the answer more useful to readers less versed in number theory. Commented Dec 25, 2017 at 17:05
• @JoonasIlmavirta, clearly the first number is divisible by $n+1$ and the second one is divisible by $2n+1$. Also, assuming any number(different from $1$) divides both of them, it must also divide $n$ which is their difference. But if it divides $n$, then it cannot divide $(2n+1)! + n + 1$, since both $(2n+1)!$ and $n$ are divisible by our divisor. Commented Dec 25, 2017 at 17:33
• @ElieLouis I know. I just thought the answer would be improved if there was some more elaboration. Right now the answer is merely a statement, albeit a true one. Commented Dec 25, 2017 at 18:00
• @JoonasIlmavirta, yes I know that you know, but I agree that it should have been clarified and so I added the information myself. Commented Dec 25, 2017 at 18:03
• Sorry, I thought it would be clear. The explanation by Elie Louis is what I had in mind. Commented Dec 25, 2017 at 18:11

I have no background in number theory, but here are my thoughts on this problem.

Let's take $n$ to be this natural number. Consider the sequence $p(k) = nk + (n-1)$. Now, this is a polynomial in $k$, so it cannot generate infinitely many primes in a row. So there must be a $K$ such that $p(K)$ is not a prime. It is clear that $p(K)$ and $p(K+1)$ are coprimes, for if any number divides both of them, then it must divide their difference, which is $n$. But this leads to a contradiction since $p(k) = n(k+1)-1$.

Now, the only part remaining to find such a $K$ such that $p(K+1)$ is not prime.

My idea here is to take $K=a(n-1)$. We can clearly see that $p(K)$ is divisible by $n-1$. What I want now is to choose $a$ such that $p(K+1)$ is composite. But notice that $p(K+1) = a(n-1)n + 2n-1$. So take $a=2n-1$. Then we have: $$(n-1)(2n-1)n + n-1$$ and $$(n-1)(2n-1)n + 2n-1$$ Both composite numbers and distant by $n$.

• +1 for showing the thought proccess, I would +10 for that if I could :D
– Ovi
Commented Dec 26, 2017 at 1:41
• Thanks :). I think the thought process is always the most important thing. Commented Dec 26, 2017 at 11:11

Suppose $p$ is a prime which is less than $n$ and not a factor of $n$ and suppose $n\equiv m \bmod p$.

If we now select odd primes $q, r$ which are not factors of $n$ with $q\equiv 1 \bmod p$ and $r\equiv p-m \bmod p$ then we have $$n=(n+qr)-qr$$The first summand is divisible by $p\lt n$ by construction, and hence is composite.

There are only the cases $n=1, 2$ which don't fit the hypothesis that there is a prime $p\lt n$ and coprime to $n$ (consider the factors of $n-1$ to confirm this). These cases are easily disposed of by $1=9-8, 2=27-25$.

The existence of the necessary primes $q,r$ is guaranteed by Dirichlet's Theorem on primes in arithmetic progression. (The special case where we can take $p=2$ is easy). Whether such a strong theorem is a necessary part of the proof, I don't know.

• As far as I can see your proof works if 'composites' is changed to 'semiprimes', is that right?
– Lehs
Commented Dec 25, 2017 at 21:22
• @Lehs I don't think I am controlling the factors of $n+qr$ enough to say that. Commented Dec 25, 2017 at 21:33