Congruences/Modular Arithmetic?

Question

Simple little proof I can't seem to get...

Prove n^21 = n^3 (mod 21) for every integer n.

that "=" sign is the three horizontal line symbol, meaning congruent.

Help please

Thanks.

I can't seem to be able to prove it properly T.T

Answer 1

You can prove the above statement if you prove that

(1) n^(21) = n^3 (mod 3) and
(2) n^(21) = n^3 (mod 7).

I'll work through (1) and let you try (2). We wish to show n^(21) = n^3 (mod 3) or n^21 - n^3 = 0 (mod 3). One way to show this is by factoring 3 consecutive integers out of it. I will do it by exhaustive casework.

Case 1: n = 0 (mod 3). Then n^21 - n^3 = 0 - 0 = 0 (mod 3).

Case 2: n = 1 (mod 3). Then n^21 - n^3 = 1 - 1 = 0 (mod 3).

Case 3: n = 2 = -1 (mod 3). Then n^21 - n^3 = -1 - (-1) = 0 (mod 3).

Thus, n^21 = n^3 (mod 3). I'll leave the rest to you (it looks a bit trickier but it shouldn't be too bad).

Answer 2

The prior answer was good.

mod 3, anything nonzero squared is just 1. And 0 to any power is just 0. So n^(any odd power) is congruent to n.

Mod 7, it's just a matter of Fermat's Little Theorem. n^7 is congruent to n; cube both sides; and you get n^21 congruent to n^3.

And since n^21 - n^3 is congruent to 0 both mod 3 and mod 7, it's divisible by both 3 and 7, and hence by 21 as well, and hence is congruent to 0 mod 21.

And there you have your proof! ;)

Answer 3

use method of induction.. good luck.. i hate proofs...