My favorite Fermat Little Theorem with Pascal Triangle

September 17, 2018Chinoiseries2014 Elementary Math, History, Math Games, Modern Math 1 Comment

Fermat Little Theorem: For any prime integer p, any integer m

$\boxed {m^{p} \equiv m \mod p}$

When m = 2,

$\boxed{2^{p} \equiv 2 \mod p}$

Note: 九章算数 Fermat Little Theorem (m=2)

Pascal Triangle (1653 AD France ）= (杨辉三角 1238 AD – 1298 AD)

$1 \: 1 \implies sum = 2 = 2^1 \equiv 2 \mod 1$

$1\: 2 \:1\implies sum = 4 = 2^2 \equiv 2 \mod 2 \;(\equiv 0 \mod 2)$

$1 \:3 \:3 \:1 \implies sum = 8= 2^3 \equiv 2 \mod 3$

1 4 6 4 1 => sum = 16= 2^4 (4 is non-prime)

$1 \:5 \:10\: 10\: 5\: 1 \implies sum = 32= 2^5 \equiv 2 \mod 5$

[PODCAST]

https://kpknudson.com/my-favorite-theorem/2017/9/13/episode-4-jordan-ellenberg

Fermat’s Little Theorem Co-prime Condition

November 27, 2014tomcircle Modern Math 1 Comment

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}}$

Elegant Proof: Fermat Little Theorem

April 10, 2013tomcircle Modern Math 1 Comment

Let’s construct a necklace with p (p being prime) beads chosen from m 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 p 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 ∎

Fermat Little Theorem

March 31, 2013tomcircle Modern Math 1 Comment

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):