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.

  • 3
    $\begingroup$ 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. $\endgroup$ Dec 25 '17 at 12:41
  • 2
    $\begingroup$ 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. $\endgroup$ Dec 25 '17 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).

  • 3
    $\begingroup$ 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. $\endgroup$ Dec 25 '17 at 17:05
  • 3
    $\begingroup$ @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. $\endgroup$
    – Higurashi
    Dec 25 '17 at 17:33
  • 7
    $\begingroup$ @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. $\endgroup$ Dec 25 '17 at 18:00
  • $\begingroup$ @JoonasIlmavirta, yes I know that you know, but I agree that it should have been clarified and so I added the information myself. $\endgroup$
    – Higurashi
    Dec 25 '17 at 18:03
  • 1
    $\begingroup$ Sorry, I thought it would be clear. The explanation by Elie Louis is what I had in mind. $\endgroup$ Dec 25 '17 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$.

  • $\begingroup$ +1 for showing the thought proccess, I would +10 for that if I could :D $\endgroup$
    – Ovi
    Dec 26 '17 at 1:41
  • $\begingroup$ Thanks :). I think the thought process is always the most important thing. $\endgroup$
    – Higurashi
    Dec 26 '17 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.

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

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.