Fermat’s Little Theorem
A French lawyer at the Parlement of Toulouse, and amateur (means lover of) Mathematician in 17th century, called
Pierre de Fermat proposed the following statement:
If p is a prime number, then for any integer n,
the number n^{p} − n is an integer multiple of p
This post is dedicated to provide the proof of statement
 Case 1: p is the divisor of n.
Lets assume n = pk since \frac{n^p  n}{p} = \frac{n(p1)}{p} = k(p  1)
 Case 2: p is not the divisor of n, which indirectly means p and n are relatively prime numbers.
We provide the proof with the help of numbers n.2n.3n.4n.\dots (p1)n
Here the key point is :
r_1 = \bmod(n,p)
r_{2} = \bmod(2n,p)
\dots
r_{p1} = \bmod(n(p1),p)
All of these reminders, which are
r_{1}, r_{2} \dots r_{p1} equals to different values.
The reason is quite straightforward! Since
n and
p are relatively numbers, multiple of
n,
which is less than
p and represented by
A can not provide this equation:
An = pB
for integer
B.
Let's try to prove this claim as well. If we can show that equation
An = pB \rightarrow \frac{A}{B} = \frac{p}{n}
does not hold, it contradicts and our claim would be proved by wellknown method, called contradiction.
Here is the point:
since
p and
n are relatively prime numbers, they don't have any common divisor.
On the other hand, since
A is less than p by problem definition, they must have one to satisfy this equation,
nevermore there is no. So, equation contradicts and now we are sure that, we can not get same
reminder of
p for numbers
k.n and
k.n + A.n where
A is less than
p.
After this proof, we need to keep going on. Before that, please notice that set of
[r_{1}, r_{2}, r_{3}, \dots r_{p1}] is equivalent to set of
[0, 1, 2 \dots p1],
since each of those reminders has to be unique as we proved by contradiction.
Here we go. The sign "
x  y " means that "x divides y".
n = p.k_{1} + r_{1} \rightarrow p  (n  r_{1})
2n = p.k_{2} + r_{2} \rightarrow p  (2n  r_{2})
3n = p.k_{3} + r_{3} \rightarrow p  (3n  r_{3})
\dots
(p1)n = p.k_{p1} + r_{p1} \rightarrow p  ( (p1)n  r_{p1})
Small Theorem
Let
a, b, c, d and
p are integers such that,
p  (a  b) and
p  (c  d). Then,
p  (ac  bd)
Small Proof
Since we have
ac  bd = ac  bc + bc  bd = c(a  b) + b(c  d), small proof is complete.
to the end...
Here, we use this small proof to conclude Fermat's Little Theorem.
Since
p  n  r_{1} and
p 2n  r_{2} we can say that:
p  [n . 2n  r_1 . r_2] \rightarrow p  [2n^{2}  r_{1}r_{2}]
Here, we can also include
3n  r_3 with our new value, since p divides both of them:
p  [3n . 2n^{2}  r_{3} . r_{2} . r_{1}]
\dots
As you can realize, we can add all numbers up to
(n  1)p
p  [n . 2n . 3n \dots (p  1)n  r_1 . r_2 . r_3 \cdots r_{p1}]
\rightarrow p  [(p  1)!n^{p1}  r_{1} . r_{2} . \cdots r_{p1}]
\rightarrow p  [(p  1)!n^{p1}  (p  1)!]
\rightarrow p  [(p  1)! (n^{p1}  1)]
\rightarrow p  [1 . 2 . 3 \dots (p  1) . (n^{p1}  1)]
Since p is a prime number and it is not divisible with numbers in between
[1, p1], it has
to be divisor of
n^{p1}  1 which concludes the proof.
p  (n^{p1}  1) \rightarrow p  (n^{p}  p)
References:

http://cims.nyu.edu/~kiryl/teaching/aa/les092403.pdf

wiki page