Fermat Little Theorem

Fermat ℓittle Theorem (FℓT)

∀ m ∈ N,
1) p prime => $Latex m^p$= m mod (p)
Note: Converse False
[Memorize Trick: military police = military in the mode of police]
Note:
p prime, ∀m,
if p | m,
=> m ≡ 0 mod (p) ...(1)
=> multiply p times:
$Latex m^p$≡ 0 mod (p) ...(2)

Substitute (1) to (2): m ≡ 0
=> p prime, ∀ m
$Latex m^p$≡ m mod (p)
=> No need (m, p) = 1 [co-prime]

E.g. (m, p) = (3, 2) =1
$Latex 3^2$= 9 ≡ 3 mod (2) ≡ 1 mod (2)
9 ≡ 1 mod (2)

E.g. (m, p) = (6, 2), p =2 |6
$Latex 6^2$= 36 ≡ 6 mod (2) ≡ 0 mod (2)
6 ≡ 0 mod (2)

WRONG EXAMPLE:  p = 4 = non prime
$Latex 2^4$= 16 ≡ 2 mod (4)
but 16 ≡ 0 mod (4)
Equivalent:
p prime => $Latex m^{p-1}$= 1 mod (p)

by Contra-positive:
3) $Latex m^{p-1}$ ≠ 1 mod (p)
=> p non-prime

Apply: Prove 39 non-prime?
Take m =2, p= 39
Prove $Latex m^{p-1}$ ≠ 1 mod (p)?
a) $Latex 2^{38} =2^{36}.2^2$ .
b) $Latex 2^6$= 64 ≡ 25 mod (39)
c) $Latex 25^2$ = 625 ≡ 1 mod (39)
From (b) & (c):

$Latex (2^6)^6$ = $latex 2^{36}$ ≡ $latex 25^6$ mod(39)≡$latex (25^2)^3$ ≡$Latex 1^3$ ≡ 1
From (a): $Latex 2^{38}$ = $Latex 2^{36}.2^2$ ≡ 1x4 ≠ 1 mod(39)
=> 39 non-prime