🎯 Fermat

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

Proof: This is a special case of Euler's Theorem.

For a prime $p$, we have $\\varphi(p) = p - 1$ (every integer from 1 to $p-1$ is coprime to $p$).

By Euler's Theorem, if $\\gcd(a, p) = 1$:

$$a^{\\varphi(p)} = a^{p-1} \\equiv 1 \\pmod{p}$$

From: Cryptography Math

Learn more: https://cryptography-xi.vercel.app/#/section/7

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