Exercise 2.3.35 (If $n$ has $k$ distinct odd prime factors, then $2^k \mid \phi(n)$.)

Question

If $n$ has $k$ distinct odd prime factors, prove that $2^k \mid \phi(n)$.

Richard Ganaye · Accepted Answer

\begin{proof} If $n$ has $k$ distinct odd prime factors, then its decomposition in prime factors is of the form
$$n = 2^{a} p_1^{a_1}\cdots p_k^{a_k},\qquad a\geq 0, \qquad a_1,\ldots,a_k \geq 1,$$
where $p_1,\ldots, p_k$ are odd primes.
 
Then $\phi(n)$ is divisible by  $p_1^{a_1-1} (p_1-1)\cdots p_k^{a_k - 1} (p_k-1)$.
For every index $i$, $2 \mid p_i -1$, therefore $2^k \mid \phi(n)$.
\end{proof}

Exercise 2.3.35 (If $n$ has $k$ distinct odd prime factors, then $2^k \mid \phi(n)$.)

Answers

Comments

Exercise 2.3.35 (If $n$ has $k$ distinct odd prime factors, then $2^k \mid \phi(n)$.)

Answers

Comments

Add answer