Results 1 to 2 of 2

Math Help - Euler's Phi Function and Chinese Remainder Theorem

  1. #1
    Junior Member
    Joined
    Jun 2008
    Posts
    39

    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
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    9
    Quote Originally Posted by duggaboy View Post
    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)).
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. The chinese remainder theorem.
    Posted in the Advanced Algebra Forum
    Replies: 2
    Last Post: June 12th 2011, 07:52 PM
  2. CRT(chinese remainder theorem)
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: August 19th 2009, 09:01 PM
  3. Chinese remainder theorem
    Posted in the Advanced Algebra Forum
    Replies: 2
    Last Post: December 15th 2008, 06:12 PM
  4. chinese remainder theorem
    Posted in the Number Theory Forum
    Replies: 5
    Last Post: May 29th 2008, 02:20 PM
  5. Chinese Remainder Theorem
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: April 10th 2006, 07:28 AM

Search Tags


/mathhelpforum @mathhelpforum