1. Not finding help here? Sign up for a free 30min tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Fermat's little theorem

  1. Apr 25, 2010 #1
    1. The problem statement, all variables and given/known data
    I'm suppose to prove that if (x,7)=1, then x to the 6th is congruent to 1 mod 7.


    2. Relevant equations



    3. The attempt at a solution
    Now, i have the proof by induction when (a,p)=1 but how do i apply this to prove it when a=x and p=7?
     
  2. jcsd
  3. Apr 25, 2010 #2
    What does Fermat's Little Theorem state?
     
  4. Apr 25, 2010 #3
    it states that if (a,p)=1 then a^(p-1) is congruent to 1 (mod p)
     
  5. Apr 25, 2010 #4
    7 is a prime, and you have that (x,7), so use Fermat's Little Theorem on x7-1 = x6
     
  6. Apr 25, 2010 #5
    so how is this for an answer?:

    since 7 is a prime and the gcd(x,7) =1, then by Fermat's Little Theorem,

    x^(7-1)=x^6 is congruent to 1(mod7)
     
  7. Apr 25, 2010 #6
  8. Apr 25, 2010 #7
    so now, if I want to show that (x^3)^2 is congruent to +/-1 (mod 7) would my work be correct? (please see the attachment).
     

    Attached Files:

Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: Fermat's little theorem
  1. Fermat Little Theorem? (Replies: 10)

Loading...