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

Can we prove the following statement ?

Every natural number $$n$$ can be written as $$n=s-t$$ ($$s,t$$ positive integers) with $$\omega(s)=\omega(t)$$ , in other words , 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$$
• What is the question? – mathreadler Jan 11 at 8:30
• If $n$ is even, then $2n$ and $n$ have the same number of prime factors, so $n = 2n-n$ is a solution – Charles Madeline Jan 11 at 8:39
• @CharlesMadeline At least we can be sure that a counterexample , if there is actually one, must be huge. – Peter Jan 11 at 9:19
• We have other possibilities. If we find a number $m$, such that $m$ and $m+1$ are both coprime to $n$ and have the same number of prime factors, we have found a solution as well. – Peter Jan 11 at 9:21
• @CharlesMadeline Moreover, we only concentrated on solutions of the form $(k+1)n-kn$. This is not required in the question. But I agree that the proof is not yet finished. – Peter Jan 11 at 9:52

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

• Nice solution ! – Kolja Jan 12 at 0:22

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