# Euler's Phi Function and Chinese Remainder Theorem

• Jun 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
• Jun 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 $\displaystyle \phi (n)$.
If $\displaystyle n>1$ and $\displaystyle n=p_1^{a_1} ... p_k^{a_k}$.
Use the formula $\displaystyle \phi(n) = p^{a_1 - 1}...p^{a_k-1} (p_1-1)(p_2-1)...(p_k-1)$.

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

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

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