> For the complete documentation index, see [llms.txt](https://cryptohack.gitbook.io/cryptobook/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://cryptohack.gitbook.io/cryptobook/fundamentals/modular-arithmetic/theorems-of-wilson-euler-and-fermat.md).

# Theorems of Wilson, Euler, and Fermat

### Wilson's Theorem

A positive integer $$n > 1$$is a prime **if and only if**:

$$
(n-1)! \equiv -1 \mod n
$$

### Euler's Theorem

Let $$n \in \mathbb{Z}^{+}$$ and $$a \in \mathbb{Z}$$ s.t. $$gcd(a, n) = 1$$, then:

$$
a^{\phi(n)} \equiv 1 \mod n
$$

### Fermat's Little Theorem

Let $$p$$be a prime and $$a \in \mathbb{Z}$$, then:

$$
a^p \equiv a \mod p
$$

or equivalently:

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

### Reference

1. [Wilson's Theorem - Brilliant](https://brilliant.org/wiki/wilsons-theorem/)
2. [Euler's Theorem - Brilliant](https://brilliant.org/wiki/eulers-theorem/)
3. [Fermat's Little Theorem - Brilliant](https://brilliant.org/wiki/fermats-little-theorem/)