prove that there are infinitely many integers n so that 3 does not divide $\phi(n)$ prove that there are infinitely many integers n so that 3 does not divide $\phi(n)$
I began to look at the problem with the residue classes of 3. I am not sure if this is correct.
 A: There are infinitely many primes of the form $3k-1$. The usual proof of the infinitude of primes works here: Given $n\ge1$, consider $(3n)!-1$, note it is relatively prime to all numbers less than or equal to $n$, and at least one of its prime factors has the form $3k-1$.
Now, $\phi(p)=p-1$ for $p$ prime, and we are done, because $3$ does not divide $3k-2$. Similarly, $\phi(p^n)=p^n-p^{n-1}=p^{n-1}(p-1)$ for $n>0$ which, again, is not divisible by $3$. Note that this subsumes the suggestions of looking at powers of $2$ or powers of $5$ given in the comments.
We can say somewhat more: $\phi(3)=2$, and of course $3$ divides $\phi(3^n)$ for $n>1$. If $p$ is a prime of the form $3k+1$, then $\phi(p^n)=p^{n-1}3k$ is a multiple of $3$ for any $n>0$. Using that $\phi$ is multiplicative, it follows that a number $n$ is such that $3$ does not divide $\phi(n)$ iff the prime factorization of $n$ involves at most one $3$, and all of its other prime factors are of the form $3k-1$.
A: referring to this answer, consider the numbers of the form $2^k, 5^k,11^k$ as well. 
