Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: 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:

Share this great discussion with others via Reddit, Google+, Twitter, or Facebook