Fermat's little theorem

p is a prime number and {a} can't be divided by p.

You use the strong induction to prove Fermat's little theorem.

∴

This is the 7th row of Pascal’s triangle.

Odd numbers are 1, and even numbers are 0.

This is fractal.

i	0	1	2	3	4	5	6	7
p	1	7	21	35	35	21	7	1

---

(p,i)≡0 mod p

(i≠0,7)

---

For example, (7,2)=7!/2!(7-2)!=5040/240=21

p!=p(p-1)!

∴

1^p≡1 mod p

This is apparent.

Therefore

2^p=(1+1)^p=1+(p,1)+(p,2)+・・・+(p,p-1)+1≡1+0+0+0+・・・+1=2 mod p

3^p=(1+2)^p=1+2(p,1)+2^2(p,2)+・・・+2^(p-1)(p,p-1)+2^p≡1+0+0+0+・・・+2=3 mod p

4^p=(1+3)^p=1+3(p,1)+3^2(p,2)+・・・+3^(p-1)(p,p-1)+3^p≡1+0+0+0+・・・+3=4 mod p

You can expand it because of Pascal’s triangle which is the binomial theorem.

(n,i)=n!/i!(n-i)!

Then you define a^(p-1).

5^16≡1 mod 17

This is also clear, so you can prove the strong induction.