Results 1 to 5 of 5

Math Help - Euler's totient function

  1. #1
    Junior Member
    Joined
    Jan 2010
    Posts
    41

    Euler's totient function

    If n=rs, r>2 and s>2, gcd(r,s)=1, show a^{\phi(n)/2} ≡ 1 (mod n).

    I really have no ideas -- something with Euler's Criterion maybe? -- any help would be appreciated. Thanks.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Senior Member roninpro's Avatar
    Joined
    Nov 2009
    Posts
    485
    You should try using the Chinese Remainder Theorem.

    It will suffice to show that a^{\varphi(n)/2}\equiv 1\pmod{r} and a^{\varphi(n)/2}\equiv 1\pmod{s} simultaneously. Keep in mind that \varphi(n)=\varphi(rs)=\varphi(r)\varphi(s).
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Junior Member
    Joined
    Jan 2010
    Posts
    41
    Quote Originally Posted by roninpro View Post
    You should try using the Chinese Remainder Theorem.

    It will suffice to show that a^{\varphi(n)/2}\equiv 1\pmod{r} and a^{\varphi(n)/2}\equiv 1\pmod{s} simultaneously. Keep in mind that \varphi(n)=\varphi(rs)=\varphi(r)\varphi(s).
    Thank you! In trying the Chinese Remainder Theorem on those two congruences, if I set x =  a^{\varphi(n)/2} , I get that N1 = rs/r = s and N2 = rs/s = r, and then I get stuck again at solving sx \equiv 1 (mod r) and rx \equiv 1 (mod s). Did I do something wrong here?
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Member
    Joined
    Jun 2010
    From
    Israel
    Posts
    148
    Note that here gcd(a,n)=1 , and therefore gcd(a,r)=gcd(a,s)=1.

    Euler's Theorem implies that a^{\phi(r)}\equiv1\bmod r; also \phi(r) is even since r\geq3. Hence a^{(\phi(r)\cdot\phi(s))/2}=(a^{\phi(r)})^{\phi(s)/2}\equiv1^{\phi(s)/2}=1\bmod r. In a similar way, we have the congruence a^{(\phi(r)\cdot\phi(s))/2}\equiv1\bmod s.

    By hypothesis gcd(r,s)=1 , so we can merge the main congruences to one that is equivalent, namely a^{\phi(r)\cdot\phi(s))/2}\equiv1\bmod rs. But \phi(n)=\phi(r)\cdot\phi(s), so a^{\phi(n)/2}\equiv1\bmod n.
    Last edited by melese; November 5th 2010 at 12:53 AM. Reason: missed division by two
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Junior Member
    Joined
    Jan 2010
    Posts
    41
    Thank you so much! I think I understand it now.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Euler's Totient Function
    Posted in the Math Challenge Problems Forum
    Replies: 2
    Last Post: July 12th 2010, 09:41 AM
  2. Euler totient function
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: February 1st 2010, 09:33 AM
  3. Euler's Totient Function
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: March 28th 2009, 07:16 PM
  4. Euler's totient function
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: December 8th 2008, 08:53 PM
  5. Euler totient function
    Posted in the Advanced Algebra Forum
    Replies: 2
    Last Post: March 25th 2007, 07:10 AM

Search Tags


/mathhelpforum @mathhelpforum