4
$\begingroup$

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$
$\endgroup$
  • 2
    $\begingroup$ What is the question? $\endgroup$ – mathreadler Jan 11 at 8:30
  • 1
    $\begingroup$ If $n$ is even, then $2n$ and $n$ have the same number of prime factors, so $n = 2n-n$ is a solution $\endgroup$ – Charles Madeline Jan 11 at 8:39
  • 1
    $\begingroup$ @CharlesMadeline At least we can be sure that a counterexample , if there is actually one, must be huge. $\endgroup$ – Peter Jan 11 at 9:19
  • 1
    $\begingroup$ 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. $\endgroup$ – Peter Jan 11 at 9:21
  • 1
    $\begingroup$ @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. $\endgroup$ – Peter Jan 11 at 9:52
3
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ Nice solution ! $\endgroup$ – Kolja Jan 12 at 0:22
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.