Results 1 to 2 of 2

Math Help - Proof an equation

  1. #1
    Newbie
    Joined
    Dec 2010
    Posts
    4

    Proof an equation

    How to proof that equation?
    a^m\equiv a^{m-\phi(m)} mod m?
    I now that if m is primes we have little fermat theorem, but what is when it is not primes. How can I proof this?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Member
    Joined
    Jun 2010
    From
    Israel
    Posts
    148
    Quote Originally Posted by oszust001 View Post
    How to proof that equation?
    a^m\equiv a^{m-\phi(m)} mod m?
    I now that if m is primes we have little fermat theorem, but what is when it is not primes. How can I proof this?
    I'm going to assume that a is relatively prime to m .

    So we have a^{\phi(m)}\equiv1\pmod m by Euler's Theorem (a generalization of Fermat's Theorem). Then we can multiply both sides by a^m to get a^{\phi(m)+m}\equiv a^m\pmod m.

    Note that (a^{\phi(m)},m)=1 since (a,m)=1; therefore we can divide both sides of a^{\phi(m)+m}\equiv a^m\pmod m by a^{\phi(m)} to get the equivalent congruence a^m\equiv a^{m-\phi(m)}\pmod m.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. [SOLVED] Proof of Equation
    Posted in the Advanced Algebra Forum
    Replies: 2
    Last Post: March 3rd 2009, 03:20 PM
  2. Please Help me proof the equation!
    Posted in the Advanced Statistics Forum
    Replies: 1
    Last Post: January 11th 2009, 12:40 PM
  3. matrix equation proof
    Posted in the Advanced Algebra Forum
    Replies: 1
    Last Post: May 6th 2008, 06:59 AM
  4. proof for an equation
    Posted in the Algebra Forum
    Replies: 5
    Last Post: April 28th 2008, 01:08 PM
  5. Differential Equation Proof
    Posted in the Calculus Forum
    Replies: 2
    Last Post: September 30th 2006, 08:34 PM

Search Tags


/mathhelpforum @mathhelpforum