Modular arithmetic?
Prove that x^7 − x ≡ 0 (mod 42) for every x ∈ Z.
I know about Fermat's little theorem which states that for p prime, x^p-1 ≡ 1 (mod p) but am unsure how to apply it here
2 Answers
- nbsale (Freond)Lv 61 month ago
x^7 - x = x(x^6 - 1)
Let's look at x^6 - 1 mod 7
FLT tells us that x^6 - 1 = 0 mod 7, so x^7 - x is always divisible by 7.
Now look at x^7 - x mod 2
If x is even so is x^7, so the difference is even, and = 0 mod 2.
If x is odd, so is x^6, so the difference is even, and = 0 mod 2
So x^7 - x is always divisible by 2.
Now look at x^6 - 1 mod 3.
FLT tells us that x^2 = mod 3, so (x^2)^3 = x^5 = 1 mod 3, and x^6 - 1 = 0 mod 3.
So x^7 - x is always divisible by 3.
Since it's divisible by 2, 3 and 7, it must be divisible by the LCM of 2, 3 and 7 = 42,
- PuzzlingLv 71 month ago
I'm not sure if you were the same anonymous person that asked this about 3 days ago, but there were a couple answers provided previously. To date, none of them has been picked as "Favorite Answer" however.
You've stated Fermat's Little Theorem as:
x^(p-1) ≡ 1 (mod p)
But it can be stated equivalently as:
x^p - x ≡ 0 (mod p)
(Subtract 1 from the first statement and multiply everything by x to see why this is true.)