Fermat Little Theorem

Fermat ℓittle Theorem (FℓT)

∀ m ∈ N,
1) p prime => 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:
m^p≡ 0 mod (p) …(2)

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

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

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

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

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

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

(2^6)^6 = 2^{36}25^6 mod(39)≡(25^2)^31^3 ≡ 1
From (a): 2^{38} = 2^{36}.2^2 ≡ 1×4 ≠ 1 mod(39)
=> 39 non-prime

One thought on “Fermat Little Theorem

  1. Pingback: Our Daily Story #1 : The Fermat’s Last Theorem | Math Online Tom Circle

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s