Problem:
Prove that there exist infinitely many positive integers such that the number of distinct odd prime factors of is a multiple of 3.
Problem:
Prove that there exist infinitely many positive integers such that the number of distinct odd prime factors of is a multiple of 3.
Solution:
Let us call , and the number of distinct odd prime factors of . We have that ; moreover, and have 2 as their only common prime factor. Indeed, suppose that is an odd prime dividing both and . Then also divides , and hence divides . But and are coprime, so divides both and , and we have thus reached a contradiction. It follows that .
Finally, observe that, if the remainders of and upon division by 3 are distinct and both different from 0, then is divisible by 3.
We want to show that, for any fixed integer , there exists an integer such that is divisible by 3.
We proceed by contradiction: assume that is not a multiple of 3 for every . Then, for every , the remainder of upon division by 3 must equal the remainder of , otherwise would be a multiple of 3. It follows that always has the same remainder for every . This, however, contradicts the fact that has remainder 2 if has remainder 1, and vice versa.