Every natural number $n$ can be written as $n=s-t$ with $\omega(s)=\omega(t)$

Question

Can we prove the following statement ?

Let $\omega(m)$ denote the number of all distinct prime factors of a positive integer $m$.

Prove that every natural number $n$ can be written as $n=s-t$, where $s$ and $t$ are positive integers with $\omega(s)=\omega(t)$, in other words, as the difference of two positive integers with the same number of distinct prime factors.

• If $n=1$ , we can choose $\ s=3\ $ and $\ t=2$.

• If $n$ is even , we can choose $\ s=2n\ $ and $\ t=n$.

Answer 1

The (generalized) Bunyakovsky conjecture implies that we always find a solution.

To show this, assume that there are infinite many positive integers $p$, such that $$2p+1$$ $$2p+3$$ $$2p^2+4p+1$$ are simultaneously prime. Then, we can choose $p>n$ satisfying this property. Then, $$(2p+1)(2p+3)n-2(2p^2+4p+1)n=n$$ is a solution, whenever $n$ is odd (the even case has already been solved).

There are plenty of other possibilities to choose the expressions, so the given statement is in fact much weaker than Bunyakovsky's conjecture.

Answer 2

There is a way to prove this directly though, and it is pretty simple:

Case 1: Both 2 and 3 divide $n$, or neither 2 nor 3 divide $n$: Then let $s=3n$ and $t=2n$.

Case 2: 3 does not divide $n$ but $2$ does: Then let $s=2n$ and $t=n$.

Case 3: 3 divides $n$ but 2 does not: Then let $p$ be the smallest odd prime that does not divide $n$. Then let $s=pn$ and let $t=(p-1)n$. [Note that $p-1$ is the product of smaller odd primes, all of which divide $n$ [by def'n of $p$], and 2, which does not. So $\omega(pn) = \omega(n) +1$ [because $p$ doesn't divide $n$], while $\omega((p-1)n) = \omega(n) +1$ as well, because the one prime factor of $p-1$ that does not divide $n$ is 2.]

Answer 3

If $d$ is any even number, Schinzel's hypothesis implies the existence of a prime $p$, such that $p+d$ is prime as well. In this case , the pair $(p,p+d)$ does the job.

Let $d$ be an odd positive integer.

$$[dx(x+y),2d\frac{x^2+xy+1}{2}]$$ is a suitable pair with difference $d$ , if all the numbers $$x,x+y,\frac{x^2+xy+1}{2}$$ are odd distinct prime numbers , all larger than the largest prime factor of $d$.

With $$p=x,q=\frac{x^2+1}{2},y=2k$$ where $p$ is an odd prime , we get the numbers $$p,p+2k,q+pk$$ Note that $q$ is an integer, if $p$ is an odd prime. Schinzel's hypothesis predicts infinite many $k$ such that all the $3$ numbers are prime because $p$ and $q$ must be coprime. Since $p$ is arbitary , we can establish large enough primes and hence get the desired solution.

So, if Schinzel's hypothesis holds, we can find a pair with every given difference.

Answer 4

• If $\ n\ $ is even, see user3733558's comments or Servaes's answer for a much simply argument than the one I originally gave.

• If $\ n\ $ is odd, let $ q\ $ be the smallest odd prime not dividing $\ n\ $. Then all the odd prime factors of $\ q-1\ $ must be factors of $\ n\ $, and both $\ qn\ $ and $\ (q-1)n\ $ must therefore have exactly one more prime factor than $\ n\ $.

Answer 5

If $n$ is even then $n$ and $2n$ have the same number of prime factors, and so $$n=2n−n,$$ shows that $n$ is the difference of two natural numbers having the same number of prime factors.

If $n$ is odd then let $q$ be the smallest odd prime number not dividing $n$. Then $q+1$ is even, and its odd factors all divide $n$. It follows that $qn$ and $(q+1)n$ have the same number of prime factors, and so $$n=(q+1)n−qn,$$ shows that $n$ is the difference of two natural numbers having the same number of prime factors.