Exercise 2.3.31 (There are infinitely many integers $n$ so that $3
mid \phi(n)$)

Question

Prove that there are infinitely many integers $n$ so that $3 
mid \phi(n)$.

Richard Ganaye · Accepted Answer

\begin{proof} Fist we prove a particular case of Dirichlet's theorem

\bigskip
{\bf Lemma.}{\it  There are infinitely many primes of the form $6k -1$.}

\begin{proof}
Suppose for contradiction that the set $A$ of primes of the form $6k - 1$ is finite, so $A = \{p_1,\ldots,p_k\}$. Consider
$$N = 6 p_1\cdots p_k - 1.$$
Then $N>1$ has prime divisors $q_1,\ldots,q_l$, where $q_i 
e 2$ since $N$ is odd, and $q_i 
e 3$ since $N \equiv -1 \pmod 3$. Such divisors are congruents to $\pm 1$ modulo 6. If all these divisors $q_i$ were congruent to $1$ modulo $6$, then $$N = q_1^{\alpha_1} \cdots q_l^{\alpha_l} \equiv 1 \pmod 6,$$
 but $N \equiv -1 \pmod 6$. Therefore $N$ has a prime divisor $q$ of the form $6 k -1$.
 
 Since $q \mid N = 6 p_1\cdots p_k - 1$, then $q 
ot \in \{p_1,\ldots,p_k\}$, otherwise $q \mid 1$, and this is impossible for a prime $q$.
 
 But $A$ is the set of all prime numbers of the form $6k+1$, thus $q \in A$, but $q 
ot \in A$. This is a contradiction, which proves that there are infinitely many primes of the form $6k -1$
 \end{proof}

A fortiori, there are infinitely many primes of the form $3k-1$. If $p = 3k - 1$ is such a prime, then $\phi(p) = p-1 = 3k-2
ot \equiv 0 \pmod 3$.
 
  There are infinitely many integers $n$ so that $3 
mid \phi(n)$ (among them are the primes $p \equiv -1 \pmod 3$).
\end{proof}

{\bf Second proof.} (I should have looked at the answers p. 514)

A shorter proof is given by $n_k = 5^k$. For any positive integer $k$,
$$3 
mid \phi(n_k)= 5^{k-1}\cdot 4$$

Exercise 2.3.31 (There are infinitely many integers $n$ so that $3 \nmid \phi(n)$)

Answers

Comments

Exercise 2.3.31 (There are infinitely many integers $n$ so that $3 \nmid \phi(n)$)

Answers

Comments

Add answer