Euler's Theorem

Euler's Theorem generalizes Fermat's Little Theorem to composite moduli using the totient function $\varphi (n)$.

Statement

Proof Idea

Let $R=\{r_1,\dots ,r_{\varphi (n)}\}$ be a reduced residue system modulo $n$. Multiply each element by $a$ to get $aR=\{a{r}_1,\dots ,a{r}_{\varphi (n)}\}$. Since $\gcd (a,n)=1$, $aR$ is just a permutation of $R$ modulo $n$. Product of $R\equiv$ Product of $aR(\mathrm{mod}n)$: Since $\gcd (P,n)=1$, we can cancel $P$ to get $1\equiv a^{\varphi (n)}$.

Power Tower (Tetration)

To compute $a^{b^c}(\mathrm{mod}n)$:

1. Reduce the base $a$ modulo $n$.
2. Reduce the exponent $b^c$ modulo $\varphi (n)$.

• To do this, reduce $c$ modulo $\varphi (\varphi (n))$, and so on.

Practice Problems