Overview

this section will go over Euler's Totient theorem, a fundamental theorem in modular arithmetic which appears in numerous competitions from AMC to USAMO.

Key Ideas

• The theorem states that for coprime integers a and n, then $a^{\phi(n)} \equiv 1$ mod n where $\phi(n)$ is equal to the number of integers $k \lt n$ which are coprime to n.

• This theorem has the advantage over Fermat's little theorem in that n is not restricted to being a prime, meaning you can apply this theorem to composite numbers.

• Euler's Totient function of an integer n calculates the quantity of numbers which are coprime to n. We can calculate this by using another theorem, namely

$\phi(n) = n \prod_{p | n} = p_{1}(1 -\frac{1}{p_{1}}) p_{2} (1- \frac{1}{p_{2}}) \cdots p_{n} (1-\frac{1}{p_{n}})$

where the product is taken over all distinct primes which divide n. Furthermore, Euler's Totient function is multiplicative, meaning that $\phi(ab) = \phi(a) \phi(b)$ for all $a,b \in \mathbb{Z}$.

Worked Example

(AoPS) Find the last 2 digits of $7^{81} - 3^{81}$.

First, notice that the last 2 digits of the expression is simply the result when taken mod 100, and $\phi(n) = 40$. Therefore we can use Euler's theorem to reduce the expression to $7^{1} - 3^{1} \equiv 04$ mod 100.

Common Pitfalls

• incorrectly calculating $\phi(n)$.
• applying the theorem when a and n are NOT coprime.
• incorrectly reducing bases.

Practice Problems