Results 1 to 5 of 5

Math Help - Euler's Theorem

  1. #1
    Newbie
    Joined
    Oct 2008
    Posts
    15

    Euler's Theorem

    I am trying to prove a little modification on Euler's theorem

    a^{\phi(n)+1}\equiv a (mod n), for all a, and where n is the product of two distinct primes say p and q.

    I am having problems with the for all a part as the above is easy to show.

    a^{\phi(n)} \equiv 1 (mod n)
    a * a^{\phi(n)} \equiv a (mod n)
    a^{\phi(n) + 1} \equiv a (mod n)

    I need to show that if q or p is a factor of a, then it still yields the same result, as Euler's theorem says that the gcd(a, n) must be 1. But I am not sure how to show that in the modification it doesn't matter. Any ideas?

    Thanks!
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Super Member PaulRS's Avatar
    Joined
    Oct 2007
    Posts
    571
    You can work with Euler's Theorem, yes.

    Well, we have that if (a,n)=1 then a^{\phi(n)}\equiv{1}(\bmod.n) and from there a^{\phi(n)+1}\equiv{a}(\bmod.n) when (a,n)=1

    Now if (a,n)>1 then p|a and/or q|a. If both divide a at the same time then n|a and the assertion is obvious since a\equiv{0}(\bmod.n) and so a^{\phi(n)+1}\equiv{0}(\bmod.n)

    So assume that only one of the prime divides a, WLOG, becuase of the symmetry consider p|a

    That is: a=p^s\cdot{k} where (k,n)=1

    Then a^{\phi(n)}=p^{s\cdot{\phi(n)}}\cdot{k^{\phi(n)}}\  equiv{p^{s\cdot{\phi(n)}}}(\bmod.n) by Euler's Theorem. That is a^{\phi(n)+1}\equiv{p^{s\cdot{(\phi(n)+1)}}\cdot{k  }}(\bmod.n)

    So it all comes down to showing that p^{s\cdot{(\phi(n)+1)}}\equiv{p^s}(\bmod.n) iff p^s\cdot{(p^{s\cdot{\phi(n)}}-1)}\equiv{0}(\bmod.n)

    And this is true since p^{s\cdot{\phi(n)}}-1\equiv{0}(\bmod.q) by Euler's Theorem ( remember that  \phi(n)=\phi(p)\cdot{\phi(q)} )
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Oct 2008
    Posts
    15
    Just to check we can say that a^{\phi(n)+1} \equiv 0(mod \dot n) when n|a is the same as a^{\phi(n)+1} \equiv a(mod \dot n) because a \equiv a(mod \dot n) for all a right?
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    10
    Quote Originally Posted by apsis View Post
    Just to check we can say that a^{\phi(n)+1} \equiv 0(mod \dot n) when n|a is the same as a^{\phi(n)+1} \equiv a(mod \dot n) because a \equiv a(mod \dot n) for all a right?
    If n|a then a^{\phi(n)+1} \equiv 0(\bmod n) (because n divides a).
    And also a\equiv 0(\bmod n).

    Remember the rule that two congruences which are congruent to the same number are congruent to eachother, and so, a^{\phi(n)+1} \equiv a(\bmod n).
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Newbie
    Joined
    Oct 2008
    Posts
    15
    Ahh, perfect I got it now! Thanks!
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 4
    Last Post: January 10th 2011, 09:51 AM
  2. How to use Euler's theorem ?
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: April 7th 2010, 10:04 AM
  3. Euler's Theorem
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: March 5th 2009, 10:07 AM
  4. Euler's Theorem
    Posted in the Number Theory Forum
    Replies: 8
    Last Post: May 5th 2008, 05:19 PM
  5. Euler's theorem
    Posted in the Advanced Algebra Forum
    Replies: 3
    Last Post: February 25th 2007, 01:53 PM

Search Tags


/mathhelpforum @mathhelpforum