Proving x^6 ≡ 1 (mod 7) Using Fermat's Little Theorem

  • Thread starter halvizo1031
  • Start date
  • Tags Tags
    Theorem
6 replies · 3K views · last reply
halvizo1031
Messages
77
Reaction score
0

Homework Statement


I'm suppose to prove that if (x,7)=1, then x to the 6th is congruent to 1 mod 7.


Homework Equations





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?
 
it states that if (a,p)=1 then a^(p-1) is congruent to 1 (mod p)
 
7 is a prime, and you have that (x,7), so use Fermat's Little Theorem on x7-1 = x6
 
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)
 
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).
 
Attachments
  • Handwritten modular arithmetic derivation: (x^3)^2 ≡ (1)^2 (mod 7) ⟺ 7 | (x^3)^2 − (1)^2 ⟺ 7 | [(x^3)^2 − 1][(x^3)^2 + 1]. Then: Since 7 is prime, 7 | (x^3)^2 − 1 or 7 | (x^3)^2 + 1 or both. If 7 | (x^3)^2 + 1, then (x^3)^2 ≡ −1 (mod 7). If 7 | (x^3)^2 − 1, then (x^3)^2 ≡ 1 (mod 7). Therefore x^3 ≡ ±1 (mod 7).
    scan0001.jpg
    23 KB · Views: 440