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
    10
    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, 08:52 PM
  2. CRT(chinese remainder theorem)
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: August 19th 2009, 10:01 PM
  3. Chinese remainder theorem
    Posted in the Advanced Algebra Forum
    Replies: 2
    Last Post: December 15th 2008, 07:12 PM
  4. chinese remainder theorem
    Posted in the Number Theory Forum
    Replies: 5
    Last Post: May 29th 2008, 03:20 PM
  5. Chinese Remainder Theorem
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: April 10th 2006, 08:28 AM

Search Tags


/mathhelpforum @mathhelpforum