Fermat's Little Theorem

$a^{p-1}\equiv 1{\pmod {p}}$
where $a$ is an integer and $p$ is a prime number.

Proof 1: Inductive Algebraic

Basis. The assertion holds for $a=0$ and $a=1$.

Induction. Assuming the assertion is true for $a$, we can show that the claim holds for $a+1$:

${\begin{aligned}(a+1)^{p}&=\sum _{k=0}^{p}{\binom {p}{k}}a^{k}1^{p-k}\\&\equiv a^{p}+1\mod {p}\\&\equiv a+1\mod {p}\\\end{aligned}}$

Therefore, the claim holds by induction on Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle a} .

quod erat demonstrandum

Proof 2: Group Theory

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mathbb{Z}_p^* = \mathbb{Z}_p \setminus \left\{ 0 \right\}} (nonzero integers modulo Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle p} ) forms a group over multiplication modulo Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle p} with order Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle p-1} . Therefore, Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle a^{p-1}} is equal to the identity element Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 1} for any Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle a \in \mathbb{Z}_p^*} .

quod erat demonstrandum

Corollary

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle a^p \equiv a \pmod{p}}