# Euler's Phi Function and Chinese Remainder Theorem

• June 2nd 2008, 04:37 PM
duggaboy
Euler's Phi Function and Chinese Remainder Theorem
I'm having difficultly understanding why φ(m) is usually divisible by 4. And then is there a systematic approach to finding φ(m) not divisible by 4?

I am thinking on the lines that its normally divisible by 4 because its relatively prime?? but that seems way to simple
• June 2nd 2008, 04:52 PM
ThePerfectHacker
Quote:

Originally Posted by duggaboy
I'm having difficultly understanding why φ(m) is usually divisible by 4. And then is there a systematic approach to finding φ(m) not divisible by 4?

I am thinking on the lines that its normally divisible by 4 because its relatively prime?? but that seems way to simple

Just write out the formula for $\phi (n)$.
If $n>1$ and $n=p_1^{a_1} ... p_k^{a_k}$.
Use the formula $\phi(n) = p^{a_1 - 1}...p^{a_k-1} (p_1-1)(p_2-1)...(p_k-1)$.

Note $p_i$'s are odd (except possibly if there is a 2 factor) and so $(p_i-1)$ is even.
Thus for $\phi(n)$ to be odd (if n is odd) it means we require $k=1$.
Thus, $n = p^k$ and so $\phi (n) = p^{k-1}(p-1)$.
For this NOT to be divisible by $4$ we require $p\equiv 3(\bmod 4)$.

Thus, $n=3^k,7^k,11^k,19^k,...$ are all examples.

The other possibility is that $n = 2^k \cdot r$, i.e. it has even factors.
Then $\phi (n) = 2^{k-1} \cdot \phi(r)$.
For this NOT to be divisible by 4 we require $k\leq 2$.
But $\phi (r)$ is even (by above) if $r>1$.
Thus, $n=2,2^2,2p$ are the only even ones not divisible by 4.
(Where $p\equiv 3(\bmod 4)$).