# exist infinitely many positive integers $n$ such $\omega (n)+\omega (n+1)\equiv 0\pmod 3$

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

• 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. Mar 29, 2019 at 1:15
• 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. Mar 29, 2019 at 1:19
• For what it's worth, $\omega(n)+\omega(n+1)$ is tabulated up to 10,000 at oeis.org/A059957/b059957.txt Mar 29, 2019 at 1:24
• @GerryMyerson,it's olympaid problem Mar 29, 2019 at 1:45
• This paper arxiv.org/pdf/1904.05096.pdf by Tao and Teravainen, solves your problem with counting function $\gg x$. May 20, 2020 at 16:52

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

$$\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}$$

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

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.

• what is $\Omega$ Mar 29, 2019 at 4:46
• the number of prime factors with multiplicity Mar 29, 2019 at 4:48