3
$\begingroup$

For integer $n>1$, $\omega (n)$ denotes number of distinct prime factors of $n$, and $\omega (1)=0$. Prove that:there exist infinitely many positive integers $n$ satisfying $$\omega (n)+\omega (n+1)\equiv 0\pmod 3$$ Positive integers $n$ satisfying $\omega(n)<\omega(n+1)<\omega(n+2)$

$\endgroup$
  • 1
    $\begingroup$ A little context, please. Is this a theorem you have come across somewhere? or a theorem you have proved, yourself? or a conjecture you are making? or a conjecture someone else made? Help us out here. $\endgroup$ – Gerry Myerson Mar 29 at 1:15
  • 2
    $\begingroup$ This is implied by the conjecture that there are infinitely many Sophie Germain primes. If $p$ is a Sophie Germain prime, $2p$ is an instance of your equation because it has two prime factors and $2p+1$ has one. $\endgroup$ – Ross Millikan Mar 29 at 1:19
  • $\begingroup$ For what it's worth, $\omega(n)+\omega(n+1)$ is tabulated up to 10,000 at oeis.org/A059957/b059957.txt $\endgroup$ – Gerry Myerson Mar 29 at 1:24
  • 1
    $\begingroup$ @GerryMyerson,it's olympaid problem $\endgroup$ – inequality Mar 29 at 1:45
  • $\begingroup$ Yes it follows from Chen's semiprime theorems $\endgroup$ – reuns Mar 29 at 2:51
6
$\begingroup$

This proof is based on some of the ideas used in the answer by reuns. Assume there are a finite # of $n$ where

$$\omega(n) + \omega(n+1) \equiv 0 \pmod 3 \tag{1}\label{eq1}$$

with $n_0$ being the largest value. Let $n_1 \gt n_0$ be an odd integer such that

$$\omega(2n_1) \equiv 0 \pmod 3 \tag{2}\label{eq2}$$

such as with $n_1 = pq$ for $2$ distinct odd primes $p$ and $q$. Next, let

$$\omega(2n_1 + 1) \equiv a \pmod 3 \tag{3}\label{eq3}$$ $$\omega(2n_1 + 2) \equiv b \pmod 3 \tag{4}\label{eq4}$$ $$\omega(2n_1 + 3) \equiv c \pmod 3 \tag{5}\label{eq5}$$ $$\omega(2n_1 + 4) \equiv d \pmod 3 \tag{6}\label{eq6}$$

The rest of this long & detailed proof will demonstrate that $a \equiv c \equiv 2 \pmod 3$ and $b \equiv d \equiv 0 \pmod 3$, i.e., the $\omega$ value congruences will always alternate between $0$ and $2$ only. To show this, first note that

$$\omega(2n_1) + \omega(2n_1 + 1) \equiv 0 + a \equiv a \not\equiv 0 \pmod 3 \tag{7}\label{eq7}$$ $$\omega(2n_1 + 1) + \omega(2n_1 + 2) \equiv a + b \not\equiv 0 \pmod 3 \tag{8}\label{eq8}$$

Since $n_1$ is odd, it would have one less distinct prime factor than $2n_1$ in \eqref{eq2}, so

$$\omega(n_1) \equiv 2 \pmod 3 \tag{9}\label{eq9}$$

As $2n_1 + 2 = 2\left(n_1 + 1\right)$, and $n_1 + 1$ is even, this means that the $\omega$ value of $n_1 + 1$ is the same as for $2n_1 + 2$ in \eqref{eq4}, so

$$\omega(n_1 + 1) \equiv b \pmod 3 \tag{10}\label{eq10}$$

Thus, since the sum of \eqref{eq9} and \eqref{eq10} can't be zero modulo $3$, this gives

$$\omega(n_1) + \omega(n_1 + 1) \equiv 2 + b \not\equiv 0 \pmod 3 \; \Rightarrow \; b \not\equiv 1 \pmod 3 \tag{11}\label{eq11}$$

Since $2n_1$ and $2n_1 + 2$ have a common factor of only $2$, this means their product has an $\omega$ value which is one less than their sum, i.e.,

$$\omega(4n_1^2 + 4n_1) = \omega(2n_1) + \omega(2n_1 + 2) - 1 \equiv b - 1 \pmod 3 \tag{12}\label{eq12}$$

Also, the square of $2n_1 + 1$ would have the same $\omega$ value, so

$$\omega(4n_1^2 + 4n_1 + 1) \equiv a \pmod 3 \tag{13}\label{eq13}$$

Adding \eqref{eq12} and \eqref{eq13} gives

$$\omega(4n_1^2 + 4n_1) + \omega(4n_1^2 + 4n_1 + 1) \equiv a + b - 1 \not\equiv 0 \pmod 3 \tag{14}\label{eq14}$$

\eqref{eq7} only allows $a \equiv 1,2 \pmod 3$. With $a \equiv 1 \pmod 3$, \eqref{eq8} and \eqref{eq11} only allow $b \equiv 0 \pmod 3$. However, this fails in \eqref{eq14}. With $a \equiv 2 \pmod 3$, \eqref{eq8} and \eqref{eq11} both give that $b \not\equiv 1 \pmod 3$ while \eqref{eq14} gives $b \not\equiv 2 \pmod 3$, so $b \equiv 0 \pmod 3$ is the only value allowed, giving that $a \equiv 2 \pmod 3$ and $b \equiv 0 \pmod 3$, with adding \eqref{eq4} & \eqref{eq5} then showing $c \not\equiv 0 \pmod 3$. Since $2n_1 + 1$ and $2n_1 + 3$ are both odd & relatively prime, the $\omega$ of their product would be the sum of their $\omega$ values from \eqref{eq3} and \eqref{eq5}, so

$$\omega(4n_1^2 + 8n_1 + 3) \equiv a + c \equiv 2 + c \pmod 3 \tag{15}\label{eq15}$$

Also, the square of $2n_1 + 2$ would have the same $\omega$ value in \eqref{eq4} so

$$\omega(4n_1^2 + 8n_1 + 4) \equiv b \equiv 0 \pmod 3 \tag{16}\label{eq16}$$

Adding \eqref{eq15} and \eqref{eq16} gives

$$\omega(4n_1^2 + 8n_1 + 3) + \omega(4n_1^2 + 8n_1 + 4) \equiv 2 + c \not\equiv 0 \pmod 3 \tag{17}\label{eq17}$$

Thus, $c \not\equiv 1 \pmod 3$ and as we determined earlier that $c \not\equiv 0 \pmod 3$, this means that $c \equiv 2 \pmod 3$. Next, checking the sum of \eqref{eq5} and \eqref{eq6} gives

$$\omega(2n_1 + 3) + \omega(2n_1 + 4) \equiv c + d \equiv 2 + d \not\equiv 0 \pmod 3 \tag{18}\label{eq18}$$

Repeating the basic procedures of above of multiplying $2n_1 + 2$ and $2n_1 + 4$, plus squaring $2n_1 + 3$, and using their $\omega$ values in \eqref{eq4} to \eqref{eq6} gives

$$\omega(4n_1^2 + 10n_1 + 8) + \omega(4n_1^2 + 10n_1 + 9) \equiv b + d - 1 + c \equiv d + 1 \not\equiv 0 \pmod 3 \tag{19}\label{eq19}$$

Thus, $d \not\equiv 2 \pmod 3$, while \eqref{eq18} gives that $d \not\equiv 1 \pmod 3$, so $d \equiv 0 \pmod 3$. However, $2n_1 + 4 = 2(n_1 + 2)$, so this mean the original $n_1$ can be replaced by $n_1 + 2$ and the above procedure repeated over and over again, giving that the $\omega$ values are always alternating between being congruent to $0$ and $2$ modulo $3$, as stated originally. Thus, the $\omega$ value will never by congruent to $1$ modulo $3$, which is of course impossible such as for cases where you have a prime number. This means the original assumption that there is only a finite # of $n$ which satisfy \eqref{eq1} must be false, i.e., there actually are an infinite # of them.

$\endgroup$
0
$\begingroup$

With $\Omega$ instead of $\omega$ I have a solution.

For any $n$ then $a = \Omega(2n) \bmod 3,b=\Omega(2n+1)\bmod 3,c=\Omega(2n+2)\bmod 3$, $\Omega((2n+1)^2) = 2b\bmod 3, \Omega((2n+1)^2-1) = a+c\bmod 3,\Omega(n)+\Omega(n+1) = a+c-2 \bmod 3$

Assume we chose $n$ such that $a=2\bmod 3$

The claim $\Omega(l)+\Omega(l+1) = 0 \bmod 3$ for some $l \in \{ 2n,2n+1, (2n+1)^2-1,n\}$ would follow from

$2+b=0\bmod 3$ or $b+c=0\bmod 3$ or $2+c+2b=0\bmod 3$ or $2+c-2=0\bmod 3$.

The only fail is when $c=2\bmod 3$.

But if $c=2\bmod 3$ we can redo it replacing $n$ by $n+1$, finding that for the claim to fail we need $\Omega(2(n+m)) = 2\bmod 3$ for every $m\ge 0$, a contradiction.

$\endgroup$
  • $\begingroup$ what is $\Omega$ $\endgroup$ – inequality Mar 29 at 4:46
  • $\begingroup$ the number of prime factors with multiplicity $\endgroup$ – reuns Mar 29 at 4:48

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.