Fermat's little theorem

Theorem 1(Theorem).

If $p$ is prime and $p ∤ a$ , then $a^{p - 1} \equiv 1 mod p$ .

Proof
Assume $p$ is prime and $p ∤ a$ . $a$ is congruent to one of $1, 2, \dots, p - 1 mod p$ . Multiply all of these by $a$ : $a, 2 a, \dots, (p - 1) a$ . We will show that this is a rearrangement of the congruence classes we started with. Clearly, none of $a, 2 a, \dots, (p - 1) a$ can be congruent to $0 mod p$ . We will now show that all of the new congruence classes are distinct. Pick two values: $r a$ , $s a$ . If $r a \equiv s a mod p$ , $(r - s) a \equiv 0 mod p$ . Thus, $p ∣ r - s$ , which can only happen if $r = s$ :
$0 < s < p ⟹ ∴ - p < r - s < p . 0 < r < p - p < - s < 0$
Thus, $a, 2 a, \dots, (p - 1) a$ is a rearrangement of $1, 2, \dots, p - 1 mod p$ . Thus,
$a \cdot 2 a \cdot \dots \cdot (p - 1) a (p - 1)! a^{p - 1} a^{p - 1} \equiv 1 \cdot 2 \cdot \dots \cdot p - 1 mod p \equiv (p - 1)! mod p \equiv 1 mod p,$
since $p ∤ (p - 1)!$ . ❏

Example 2(Example).

ghci> a=[1..10]
[1,2,3,4,5,6,7,8,9,10]
ghci> map (\x-> mod x 11) (map (*2) a)
[2,4,6,8,10,1,3,5,7,9]
ghci> map (\x-> mod x 11) (map (*3) a)
[3,6,9,1,4,7,10,2,5,8]
ghci> map (\x-> mod x 11) (map (*4) a)
[4,8,1,5,9,2,6,10,3,7]
ghci> map (\x-> mod x 11) (map (*5) a)
[5,10,4,9,3,8,2,7,1,6]
ghci> map (\x-> mod x 11) (map (*6) a)
[6,1,7,2,8,3,9,4,10,5]
ghci> map (\x-> mod x 11) (map (*7) a)
[7,3,10,6,2,9,5,1,8,4]
ghci> map (\x-> mod x 11) (map (*8) a)
[8,5,2,10,7,4,1,9,6,3]
ghci> map (\x-> mod x 11) (map (*9) a)
[9,7,5,3,1,10,8,6,4,2]
ghci> map (\x-> mod x 11) (map (*10) a)
[10,9,8,7,6,5,4,3,2,1]

Can be packaged up in a matrix:

12345678910246810135793691471025848159261037510493827166172839410573106295184852107419639753110864210987654321

Example 1.1.9: It can be deduced from Fermat’s little theorem that every element in $(Z / p Z)^{\times}$ has an inverse: For any $a \in (Z / p Z)^{\times}$ , one of $a, 2 a, \dots, (p - 1) a$ must be $1$ . We can also see why this doesn’t work when $p$ is not prime. For example, if $p = 10$ , the matrix is

123456789246802468369258147482604826505050505628406284741852963864208642987654321 * * * * .

Only elements which are co-prime with 10 have inverses. Those not co-prime with 10 fall into cycles, and can never reach $10 k + 1$ since they always reach $10 k$ .

NoNotes

Graph View

Fermat's little theorem

Backlinks