# Fermat's Little Theorem/Proof 2

## Theorem

Let $p$ be a prime number.

Let $n \in \Z_{>0}$ be a positive integer such that $p$ is not a divisor of $n$.

Then:

$n^{p - 1} \equiv 1 \pmod p$

## Proof

$p \nmid n \implies p \perp n$

and Euler's Theorem can be applied.

Thus:

$n^{\map \phi p} \equiv 1 \pmod p$

But from Euler Phi Function of Prime Power:

$\map \phi p = p \paren {1 - \dfrac 1 p} = p - 1$

and the result follows.

$\blacksquare$