📐 Euler

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

Proof: Generalizes Fermat's proof. Multiplication by $[a]$ permutes $G_n$. Product of $[a]G_n$ is $[a]^{\\phi(n)}$ times product of $G_n$. Cancel to get $[a]^{\\phi(n)} = [1]$.

From: intro-discrete

Learn more: https://mathacademy-cyan.vercel.app/#/section/5

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