# If $n$ has $r$ odd prime divisors then $2^r | \phi(n)$

Let $\phi (n)$ be the Euler totient function $n\in \Bbb N$. If $n$ has $r$ odd prime divisors then $2^r | \phi(n)$

If $n$ is prime then $\phi(n)= n-1$ except $2$ all primes are odd therefore $n-1$ would be even and $2^r$ a divisor.

What should I do if $n$ is not prime?

• Perhaps the correct statement is "If $n$ has $r$ odd prime divisors, ....". – lhf May 11 '17 at 22:35

If $n$ is not prime, then $n=p_1^{\alpha_1}\cdots p_r^{\alpha_r}$, and $\phi(n)=n\prod_{i=1}^r\left(1-\frac{1}{p_i}\right)$. Rewriting the parenthetical as $\frac{p_i-1}{p_i}$,we see that $p_i$ will divide $n$ (since each $\alpha_i\geq 1)$ and there are $r$ terms of $p_i-1$ each of which is even (since $p_i$ are odd). Hence $2^r$ will divide the numerator.

• We were given that there are $r$ odd prime divisors, so $2$ is not a problem. – Ross Millikan May 12 '17 at 5:10