📐 Fermat

If $p$ is prime and $\\gcd(a, p) = 1$, then $a^{p-1} \\equiv 1 \\pmod{p}$.

Proof: Consider the residues $a, 2a, 3a, \\ldots, (p-1)a \\pmod{p}$. These are a permutation of $1, 2, \\ldots, p-1$ since $\\gcd(a,p)=1$ prevents any two from being congruent.

Multiplying all together: $a \\cdot 2a \\cdot 3a \\cdots (p-1)a \\equiv 1 \\cdot 2 \\cdot 3 \\cdots (p-1) \\pmod{p}$

This giv...

From: Disquisitiones Arithmeticae

Learn more: https://gauss-deploy.vercel.app/#/section/2

Explore all courses: https://mathacademy-cyan.vercel.app