Euler's Theorem and Euler's Totient Function

Euler's Totient Function $\varphi(n)$

$\varphi(n)$ counts how many integers from 1 to $n$ are coprime to $n$ (share no common factor other than 1).

Step-by-step: Compute $\varphi(36)$

Method 1 — Direct counting:

List integers 1 to 36 and check which are coprime to 36 (i.e., $\gcd(k, 36) = 1$):

$36 = 2^2 \times 3^2$. So we exclude multiples of 2 and multiples of 3.

Coprime to 36: $1, 5, 7, 11, 13, 17, 19, 23, 25, 29, 31, 35$. Count: 12.

Method 2 — Formula:

For $n = p_1^{a_1} \times p_2^{a_2} \times \cdots$:

$\varphi(n) = n \left(1 - \frac{1}{p_1}\right)\left(1 - \frac{1}{p_2}\right) \cdots$

For $36 = 2^2 \times 3^2$:

$\varphi(36) = 36 \left(1 - \frac{1}{2}\right)\left(1 - \frac{1}{3}\right) = 36 \times \frac{1}{2} \times \frac{2}{3} = 36 \times \frac{1}{3} = 12$

$\boxed{\varphi(36) = 12}$

Euler's Theorem

If $\gcd(a, n) = 1$, then:

$a^{\varphi(n)} \equiv 1 \pmod{n}$

This generalizes Fermat's little theorem (which is the special case where $n$ is prime, so $\varphi(n) = n - 1$).

Step-by-step: Find $7^{100} \mod 36$

Step 1: $\gcd(7, 36) = 1$ ✓ and $\varphi(36) = 12$.

Step 2: By Euler's theorem, $7^{12} \equiv 1 \pmod{36}$.

Step 3: $100 = 12 \times 8 + 4$, so $7^{100} = (7^{12})^8 \times 7^4 \equiv 1^8 \times 7^4 \equiv 7^4 \pmod{36}$.

Step 4: $7^2 = 49 \equiv 13 \pmod{36}$. $7^4 = 13^2 = 169 \equiv 169 - 4 \times 36 = 169 - 144 = 25 \pmod{36}$.

$\boxed{7^{100} \equiv 25 \pmod{36}}$

Special values of $\varphi$

• $\varphi(p) = p - 1$ for prime $p$
• $\varphi(p^k) = p^k - p^{k-1} = p^{k-1}(p-1)$
• $\varphi$ is multiplicative: $\varphi(mn) = \varphi(m)\varphi(n)$ when $\gcd(m,n) = 1$

Try it in the visualization

Enter $n$. The integers 1 to $n$ are displayed — those coprime to $n$ are highlighted. The count gives $\varphi(n)$. Then enter base $a$ and exponent $e$ to compute $a^e \mod n$ using Euler's theorem.