Prove Fermat Little Theorem $ a^p \equiv a \mod p \quad \gcd(a, p) = 1 \text{, p is prime} \text{ [Method 1]}$

Use binomial theorem to prove Fermat Little Theorem

$\text{Binomial Theorem }(a + b)^n = \sum_{k=0}^{n} \binom{n}{k} a^k b^{n-k}$

$\text{Let n = p}$

$\Rightarrow (a + b)^p = \sum_{k=0}^{p} \binom{p}{k} a^k b^{p-k}$

$\text{Lemma 1 }(a + b)^p = a^{p} + b^{p} \mod p$

$\text{Proof}$

$(a + b)^p = b^p + \frac{p!}{(p-1)!}a^1 b^p + \frac{p!}{(p-2)! 2!}a^2 b^{p-2} + ... + \frac{p!}{(1)! (p-1)!}a^{p-1} b^{1} + a^p$

$ p \nmid k \text{ and } p \nmid (p-k)\quad \therefore \text{ p is prime and } 0 \lt k \lt p $

$ \Rightarrow \binom{n}{k} = 0 \mod p \quad \therefore 0 \lt k \lt p$

$ \Rightarrow (a + b)^{p} \equiv a^{p} + b^{p} \mod p $

$ \text{Let b = 1}$

$ \Rightarrow (a + 1)^{p} \equiv a^{p} + 1 \mod p $

$ \text{Assume } a^{p} \equiv a \mod p \quad \text{(Use induction)}$

$ \Rightarrow (a + 1)^{p} \equiv a + 1 \mod p \quad \square$

Prove Fermat Little Theorem $ a^p \equiv a \mod p \quad \gcd(a, p) = 1 \text{, p is prime} \text{ [Method 2]}$

$\text{Let } 1 \le k \le p-1$

$ \because p \nmid k \text{ and } p \nmid a $

$ \therefore p \nmid ka \quad\quad\quad\quad\quad\quad\quad \text{(1)}$

$ \Rightarrow 1 \le ka \mod p \le p-1$

$ \text{Let } k_i \lt k_j \therefore 1 \le k_j-k_i \le p-1$

$ k_ja \equiv x \mod p \quad\quad\quad\quad \text{(2)}$

$ k_ia \equiv y \mod p \quad\quad\quad\quad \text{(3)}$

$ \text{Assume } x = y$

$ \Rightarrow (k_j-k_i)a \equiv 0 \mod p$

$ \Rightarrow p \mid (k_j-k_i)a \quad \text{this contradicts (1)}$

$ \Rightarrow x \neq y \text{ if } k_j \neq k_i$

$ \text{From (1) and (2)}$

$ \Rightarrow 1a*2a*...*(p-1)a = (p-1)!a^{p-1} \equiv (p-1)! \mod p$

$ \Rightarrow a^{p-1} \equiv 1 \mod p$

$ \Rightarrow a^{p} \equiv a \mod p \quad \square$