Fermat’s Little Theorem Co-prime Condition

It is confusing for students regarding the two forms of the Fermat’s Little Theorem, which is the generalization of the ancient Chinese Remainder Theorem (中国剩馀定理) — the only theorem used in modern Computer Cryptography .

General: For any number a

\boxed { a^p \equiv a \mod p, \forall a}

We get,
a^{p} - a \equiv 0 \mod p
a. (a^{(p-1)} -1) \equiv 0 \mod p
p \mid a.(a^{(p-1)} -1)
If (a, p) co-prime, or g.c.d.(a, p)=1,
then p cannot divide a,
thus
p \mid (a^{(p-1)} -1)
a^{(p-1)} -1 \equiv 0 \mod p

Special: g.c.d. (a, p)=1

\boxed {a^{(p-1)} \equiv 1 \mod p, \forall a \text { co-prime p}}

image

Advertisements

Elegant Proof: Fermat Little Theorem

Let’s construct a necklace with p (p being prime) beads chosen from distinct colors.
There will be m^p permutations of necklaces
less:
1. m permutations of necklaces with beads of same color;
2. Joining the 2 ends of the necklace to form a loop. For prime p beads, there will be cyclic permutations of beads which are the same.

Total distinct necklaces = (m^p – m) / p  …[*]
which is an integer, ie p divides (m^p – m)
m^p – m ≡ 0 (mod p)
or m^p  ≡ m (mod p) if p prime  ∎

From [*],  m.[m^(p-1) – 1] / p
If m and p are relatively prime, i.e. (m, p) = 1
then p divides (m^(p-1) – 1),
m^(p-1)  – 1≡ 0 (mod p)
or
m^(p-1) ≡ 1 (mod p)  if  p prime & (m, p) = 1 ∎

Group: Fermat Little Theorem

Use Group to prove Fermat Little Theorem:
For any prime p,
Let Group (Zp,*mod p) = {1,2,3….p-1};    [*mod p= multiply modulo p]
For any non-zero m in Zp,
m^{p-1} = 1 \: \mbox { in Zp }
Since Zp isomorphic~ to the ring of co-sets  of the form m+pZ   (eg. Z2 ~ {0+2Z, 1+2Z}
For any m in Z not in the co-set {0+pZ}
ie m ≠0 (mod p)
or p not divisible by m
m^{(p-1)} \equiv 1 \mod p, \forall m \text{ coprime p}

For general case: no need the (m, p) co-prime condition

(x m both sides)

\boxed{    m^{p} \equiv m \mod p, \forall m }

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