The difference of two coprime composites

Question

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.

Answer 1

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).

Answer 2

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.

Answer 3

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$.