# Several Theorems in Number Theory
## Notation
$[x]:=\{1, 2, \dots, x\}$
$p$ is always a prime.
$\phi(n):=\{x|x\in[n-1], \gcd(x, n)=1\}$
## Lemma 1
$\forall a, b, c\in[p-1],\ ab\equiv ac\mod p\iff b\equiv c\mod p$
### Proof
It's easy to know that $b\equiv c\mod p\Rightarrow ab\equiv ac\mod p$.
If $ab\equiv ac\mod p$, then $a(b-c)\equiv 0\mod p$.
$\because p\nmid a\Rightarrow p|b-c\Rightarrow b\equiv c\mod p$.
## Fermat's Little Theorem
$a^{p-1}\equiv 1\mod p$
### Proof
From Lemma1, we can conclude that $\because\forall a\in[p-1],\ a\not\equiv2a\not\equiv\dots\not\equiv(p-1)a\mod p$,
$\Rightarrow a, 2a, \dots, (p-1)a$ is a permutation of $1, 2, \dots, p-1$.
Therefore, $a^{p-1}(p-1)!\equiv a\times2a\times\dots\times(p-1)a\equiv 1\times2\times\dots\times(p-1)\equiv(p-1)!\mod p$
$\Rightarrow a^{p-1}\equiv 1\mod p$.
## Lemma 2
$\forall\gcd(a, p)=1,\ a^{\phi(p^k)}(=a^{(p-1)p^{k-1}})\equiv1\mod p^k$
### Proof
Let's use induction on $k$ to prove the lemma.
For $k=1$, by Fermat's Little Theorem, we know that the lemma holds.
Suppose that when $k=k'$, the lemma holds.
When $k=k'+1$, let $a^{\phi(p^{k'})}=bp^{k'}+1$,
$a^{\phi(p^{k'+1})}=(bp^{k'}+1)^p=\sum_{i=0}^p\binom{p}{i}b^ip^{ik'}\equiv\binom{p}{1}bp^{k'}+\binom{p}{0}\equiv 1\mod p^{k'+1}$, which implies the lemma holds.
Therefore, by induction, the lemma holds $\forall k\in\mathbb{N}$.
## Euler Theorem
$\forall\gcd(a, n)=1,\ a^{\phi(n)}\equiv1\mod n$
### Proof
Let $n=\prod_{i=1}^mp_i^{k_i}$.
$\because\phi(n)=n\times\prod_{i=1}^m\frac{p_i-1}{p_i}=\prod_{i=1}^m\phi(p_i^{k_i})$
$\Rightarrow a^{\phi(n)}\equiv \left(a^{\phi(p_i^{k_i})}\right)^{\frac{\phi(n)}{\phi(p_i^{k_i})}}\equiv 1\mod p_i^{k_i}$.
$\therefore a^{\phi(n)}\equiv 1\mod \prod_{i=1}^mp_i^{k_i}\equiv 1\mod n$.
## Wilson's Theorem
$(p-1)!\equiv -1\mod p$
### Proof
From Lemma1, we know that for all $a\in[p-1]$, there exists an unique $b\in[p-1]$ such that $ab\equiv 1\mod p$.
If $a^2\equiv 1\mod p$, then $p|(a+1)(a-1)$, which means $a\equiv\pm 1\mod p$.
Therefore, for elements in $[p-1]\setminus\{1, p-1\}$, each element $a$ is paired with another element $b$ such that $ab\equiv 1\mod p$
$\Rightarrow(p-1)!\equiv 1\cdot1\cdot(p-1)\equiv -1\mod p$.