Prove that there are infinitely many integers $n$ such that $3\nmid\phi(n)$

Question

My thoughts are to choose any number of the form $2^k$, $5^k$ or any number combined of both of these two like $10,50,100$ and so on. The reasoning follows from the closed form of $\phi(n)$. Sorry for the duplication to this question but I feel this proof is much easier and natural to come up with. Is that right?

Answer 1

Your solutions are correct. Indeed $$\varphi(2^k)=2^{k-1}\quad \&\quad \varphi(5^k)=5^{k-1}\times 4$$

It is easy to generate more examples, such as $$\varphi(11^k)=11^{k-1}\times 10\quad \text {or}\quad \varphi(17^k)=17^{k-1}\times 16$$

Answer 2

Let $n = p_1^{k_1} p_2^{k_2} \cdots p_m^{k_m}$. Recall that you have $\phi(p^k) = p^{k-1} (p-1)$, and $\phi$ is a multiplicative function -- that is,

$$ \phi(p_1^{k_1} p_2^{k_2} \cdots p_m^{k_m}) = \prod_{i=1}^m p_i^{k_i-1} (p_i-1) $$

For the right hand side to be divisible by 3, it must have a factor that's divisible by 3. For a factor of 3 to come from $p_i^{k_i-1}$ we must have $p_i = 3$ and $k_i \ge 2$ - that is, $n$ is divisible by $3^2$. For a factor of 3 to come from $p_i - 1$, $p_i$ must be one more than a multiple of 3.

So $\phi(n)$ is not divisible by 3 if, and only if, it has no prime factors of form $3j + 1$ and at most one prime factor of $3$. It's clear that there are infinitely many such numbers, for example those families given by lulu. The sequence is at https://oeis.org/A088232.