Theorems of Wilson, Euler, and Fermat

Wilson's Theorem

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

(n1)!1modn(n-1)! \equiv -1 \mod n

Euler's Theorem

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

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

Fermat's Little Theorem

Let ppbe a prime and aZa \in \mathbb{Z}, then:

apamodpa^p \equiv a \mod p

or equivalently:

ap11modpa^{p-1} \equiv 1 \mod p