Show that there are infinitely many positive integers $n$ such that the number of distinct odd prime factors of $n(n + 3)$ is a multiple of $3$.
I couldn't get much progress, I took $n= 3k$, and then was trying to show, that there are infinitely many many positive integers $k$ such that the number of distinct odd prime factors of $k(k + 1)$ is $1\mod 3$.
So if I can show that
There are infinitely many triangular numbers which are of the form $qp$ , where $p,q$ is a prime
This looks true seeing the OEIS Link , the first term is $55$, then $91$ , then $231$ and so on ..
then I will be done.
However, I think I am in a wrong path, because it's a contest problem.
Thanks in advance!
Here's the link of the question
Best Answer
Here's a different method to solve the contest problem. Assume there's only a finite number of positive integers $n$ where the number of distinct odd prime factors of $n(n + 3)$ is a multiple of $3$. Thus, there's a maximum integer $n_0$ where this holds so, for all $n \gt n_0$, the number of distinct odd prime factors of $n(n + 3)$ is not a multiple of $3$. Note all of the integers used below are considered to be $\gt n_0$. Next, define
$$f(i) = \text{the number of distinct prime factors } \ge 5 \text{ of } i \tag{1}\label{eq1A}$$
One other thing to note is there is no prime factor $\ge 5$ in common among any two integers in a group of $4$ consecutive integers.
Similar to what you did, the product of any $2$ consecutive integers, say $m(m + 1)$, can be multiplied by $9$ to get $3m(3m + 3)$, which is of the form of $n(n + 3)$ with $n = 3m$. The finiteness assumption means that $1$ (for the factor of $3$) plus the number of distinct odd prime factors $\ge 5$ of $n(n + 3)$ (and also $m(m + 1)$) can't be a multiple of $3$. Thus, this means for any $2$ consecutive integers $m$ and $m + 1$, since the $f(i)$ function doesn't include the factor of $3$, we get
$$f(m(m + 1)) = f(m) + f(m + 1) \not\equiv 2 \pmod{3} \tag{2}\label{eq2A}$$
Squaring doesn't change the number of distinct prime factors, so $f(j^2) = f(j)$. Thus,
$$f((j^2 - 1)j^2) = f(j^2 - 1) + f(j^2) = f(j - 1) + f(j) + f(j + 1) \tag{3}\label{eq3A}$$
Using this, along $m = j^2 - 1$ in \eqref{eq2A}, gives
$$f(j - 1) + f(j) + f(j + 1) \not\equiv 2 \pmod{3} \tag{4}\label{eq4A}$$
Choose an $n_1$ where $3 \mid n_1$ and $f(n_1) \equiv 2 \pmod{3}$ (e.g., $n_1$ is $3$ times the product of $2$ large primes). Next, for somewhat simpler algebra, define
$$d_i = f(n_1 + i), \; i \ge 0 \tag{5}\label{eq5A}$$
which means
$$d_0 \equiv 2 \pmod{3} \tag{6}\label{eq6A}$$
Using \eqref{eq2A} (with $m = n_1$ in \eqref{eq7A} and $m = n_1 + 1$ in \eqref{eq9A}), \eqref{eq4A} (with $j - 1 = n_1$ in \eqref{eq8A}) and \eqref{eq5A} gives
$$d_0 + d_1 \not\equiv 2 \pmod{3} \tag{7}\label{eq7A}$$
$$d_0 + d_1 + d_2 \not\equiv 2 \pmod{3} \tag{8}\label{eq8A}$$
$$d_1 + d_2 \not\equiv 2 \pmod{3} \tag{9}\label{eq9A}$$
Using \eqref{eq6A} in \eqref{eq8A} gives $d_1 + d_2 \not\equiv 0 \pmod{3}$. Combined with \eqref{eq9A}, this gives
$$d_1 + d_2 \equiv 1 \pmod{3} \tag{10}\label{eq10A}$$
Using \eqref{eq6A} in \eqref{eq7A} gives $d_1 \not\equiv 0 \pmod{3}$. If $d_1 \equiv 2 \pmod{3}$, then \eqref{eq10A} gives $d_2 \equiv 2 \pmod{3}$. Note, though, in this case, we can then repeatedly use \eqref{eq8A}, \eqref{eq9A} and \eqref{eq10A}, with the indices being incremented by $1$ each time, to get that $d_i \equiv 2 \pmod{3}$ for all $i \ge 0$. However, this is not possible, e.g., where a $n_1 + i$ value is a prime number. Thus, this means we must instead have
$$d_1 \equiv 1 \pmod{3} \tag{11}\label{eq11A}$$
Therefore, \eqref{eq10A} gives
$$d_2 \equiv 0 \pmod{3} \tag{12}\label{eq12A}$$
Reusing \eqref{eq8A} and \eqref{eq9A} with the indices increased by $1$ results in
$$d_1 + d_2 + d_3 \not\equiv 2 \pmod{3} \tag{13}\label{eq13A}$$
$$d_2 + d_3 \not\equiv 2 \pmod{3} \tag{14}\label{eq14A}$$
Using \eqref{eq11A} in \eqref{eq13A} gives $d_2 + d_3 \not\equiv 1 \pmod{3}$. Combined with \eqref{eq14A} gives
$$d_2 + d_3 \equiv 0 \pmod{3} \tag{15}\label{eq15A}$$
Using \eqref{eq12A} in \eqref{eq15A} gives
$$d_3 \equiv 0 \pmod{3} \tag{16}\label{eq16A}$$
Using $3 \mid n_1$ with $f(n_1(n_1 + 3))$ and our finiteness assumption means that
$$d_0 + d_3 \not\equiv 2 \pmod{3} \tag{17}\label{eq17A}$$
However, using \eqref{eq6A} in \eqref{eq17A} gives
$$d_3 \not\equiv 0 \pmod{3} \tag{18}\label{eq18A}$$
This contradicts \eqref{eq16A}. Since we have shown that both of the $2$ allowed cases for the congruence of $d_1 \pmod{3}$ can't hold, this means the original finiteness assumption, i.e., there's only a finite number of $n$ which work, must be incorrect. This proves there are an infinite number of positive integers $n$ where the number of distinct odd prime factors of $n(n + 3)$ is a multiple of $3$.