1. Limited time only! Sign up for a free 30min personal 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!

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