Euler's Phi Function and Chinese Remainder Theorem

**duggaboy** · June 2nd 2008, 04:37 PM

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

**ThePerfectHacker** · June 2nd 2008, 04:52 PM

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)$ ).

Thread: Euler's Phi Function and Chinese Remainder Theorem

LinkBack

Thread Tools

Display

Euler's Phi Function and Chinese Remainder Theorem

Similar Math Help Forum Discussions

The chinese remainder theorem.

CRT(chinese remainder theorem)

Chinese remainder theorem

chinese remainder theorem

Chinese Remainder Theorem

Search Tags