10
$\begingroup$

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.

$\endgroup$
2
  • 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$ Commented Dec 25, 2017 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$ Commented Dec 25, 2017 at 14:48

3 Answers 3

17
$\begingroup$

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

$\endgroup$
5
  • 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$ Commented Dec 25, 2017 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
    Commented Dec 25, 2017 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$ Commented Dec 25, 2017 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
    Commented Dec 25, 2017 at 18:03
  • 1
    $\begingroup$ Sorry, I thought it would be clear. The explanation by Elie Louis is what I had in mind. $\endgroup$ Commented Dec 25, 2017 at 18:11
9
$\begingroup$

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

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

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.

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

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .