Results 1 to 3 of 3

Math Help - prove by fermat-euler

  1. #1
    Senior Member
    Joined
    Feb 2008
    Posts
    321

    prove by fermat-euler

    Attached Thumbnails Attached Thumbnails prove by fermat-euler-1.jpg  
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Newbie
    Joined
    Feb 2008
    Posts
    17
    Fermat's Little Theorem has a very nice proof ...

    Take p is prime and x>0. (You have already stated that p does not divide x).
    You can easily prove that \left\{x,2x,...,(p-1)x\right\}=\left\{1,2,...,p-1\right\} (a basic proof by contradiction should do the trick).
    Hence it must be the case that x*2x*...*(p-1)x\equiv_{p}1*2*...*(p-1).
    You can then collect the x terms and observe that x^{p-1}(1*2*...*(p-1)\equiv_{p}1*2*...*(p-1).
    From this it follows that x^{p-1}\equiv_{p}1 as required

    Hope that helps

    Paul
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    9
    Say that \gcd (x,n)=1 and n=mp.
    If x^{n-1}\equiv 1(\bmod p) then it means x^{mp-1}\equiv 1(\bmod p) thus x^{m-1}\equiv 1(\bmod p).
    If x^{m-1}\equiv 1(\bmod p) then \left ( x^{m-1} \right)^p \equiv 1(\bmod p) so x^{mp -p}\equiv 1(\bmod p) thus x^{n - 1}\equiv(\bmod p).

    We never used the condition \gcd( m,p)=1 anywhere. We do not need it. Generalize this to several primes.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 4
    Last Post: January 10th 2011, 08:51 AM
  2. Working with mod p (Euler's and Fermat's Theorem)
    Posted in the Advanced Algebra Forum
    Replies: 1
    Last Post: April 22nd 2010, 11:22 PM
  3. Use induction to prove Fermat's Little Theorem
    Posted in the Advanced Algebra Forum
    Replies: 3
    Last Post: March 8th 2010, 05:36 PM
  4. Replies: 0
    Last Post: September 17th 2009, 06:44 PM
  5. fermat,euler,or CRT?
    Posted in the Number Theory Forum
    Replies: 5
    Last Post: January 4th 2008, 02:08 PM

Search Tags


/mathhelpforum @mathhelpforum