Results 1 to 2 of 2

Thread: Proof an equation

  1. #1
    Newbie
    Joined
    Dec 2010
    Posts
    4

    Proof an equation

    How to proof that equation?
    $\displaystyle 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?
    $\displaystyle 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 $\displaystyle a $ is relatively prime to $\displaystyle m $.

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

    Note that $\displaystyle (a^{\phi(m)},m)=1$ since $\displaystyle (a,m)=1$; therefore we can divide both sides of $\displaystyle a^{\phi(m)+m}\equiv a^m\pmod m$ by $\displaystyle a^{\phi(m)}$ to get the equivalent congruence $\displaystyle 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: Mar 3rd 2009, 03:20 PM
  2. Please Help me proof the equation!
    Posted in the Advanced Statistics Forum
    Replies: 1
    Last Post: Jan 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: Apr 28th 2008, 01:08 PM
  5. Differential Equation Proof
    Posted in the Calculus Forum
    Replies: 2
    Last Post: Sep 30th 2006, 08:34 PM

Search Tags


/mathhelpforum @mathhelpforum