📐 Euler

If $\\gcd(a, n) = 1$, then $a^{\\varphi(n)} \\equiv 1 \\pmod{n}$.

Proof: **Proof Sketch:**

1. Let $\\{r_1, r_2, \\ldots, r_{\\varphi(n)}\\}$ be the reduced residue system mod $n$ (all integers coprime to $n$ in $[1, n-1]$).

2. Since $\\gcd(a, n) = 1$, the set $\\{a \\cdot r_1, a \\cdot r_2, \\ldots, a \\cdot r_{\\varphi(n)}\\}$ is also a reduced residue system mod $...

From: Cryptography Math

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

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