# 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$