## Trending News

# 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

- ?Lv 62 months 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 72 months 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.)