Fermat’s Little Theorem
If $p$ is a prime number and $a$ is an integer not divisible by $p$, then:
$a^{p-1} \equiv 1 \pmod{p}$
Euler’s Theorem
If $\gcd(a, n) = 1$, then:
$a^{\varphi(n)} \equiv 1 \pmod{n}$
where $\varphi(n)$ is Euler’s totient function.
Chinese Remainder Theorem
If $n_1, n_2, \dots, n_k$ are pairwise coprime, then the system:
\begin{cases}
x \equiv a_1 \pmod{n_1}
x \equiv a_2 \pmod{n_2}
\vdots
x \equiv a_k \pmod{n_k}
\end{cases}
has a unique solution modulo $N = n_1n_2\cdots n_k$.
Wilson’s Theorem
For a prime $p$:
(p-1)! \equiv -1 \pmod{p}
Lagrange’s Four Square Theorem
Every natural number can be written as the sum of four integer squares:
n = a^2 + b^2 + c^2 + d^2
for some integers $a, b, c, d$.
Dirichlet’s Theorem on Primes in Arithmetic Progressions
If $\gcd(a, d) = 1$, then the arithmetic sequence:
a, a+d, a+2d, a+3d, \dots
contains infinitely many prime numbers.
Bertrand’s Postulate
For every integer $n > 1$, there exists at least one prime $p$ such that:
n < p < 2n