Math Core

Almost every AIME has a problem that asks for the remainder of an enormous power, like $7^{2026}$ or a tower such as $7^{7^7}$ , when divided by some modulus. You can't compute these numbers, but you don't have to. Fermat's and Euler's theorems tell you that powers repeat, and exactly how often, so a giant exponent shrinks to a small one.

Fermat's little theorem

If $p$ is prime and $p \nmid a$ , then

$a^{p-1} \equiv 1 \pmod p.$

Equivalently, $a^p \equiv a \pmod p$ for every integer $a$ (including multiples of $p$ ).

Why it's true. Look at the $p - 1$ numbers

$a, \ 2a, \ 3a, \ \dots, \ (p-1)a.$

None of them is divisible by $p$ , and no two are congruent mod $p$ : if $ia \equiv ja$ , then $p \mid (i - j)a$ , and since $p \nmid a$ we get $p \mid i - j$ , which forces $i = j$ . So these $p - 1$ numbers are just $1, 2, \dots, p-1$ in some scrambled order mod $p$ . Multiply them all together:

$a^{p-1} \cdot (p-1)! \equiv (p-1)! \pmod p.$

Since $(p-1)!$ is not divisible by $p$ , you can cancel it, leaving $a^{p-1} \equiv 1$ .

How to use it. Mod a prime $p$ , exponents only matter mod $p - 1$ . To find $5^{100} \bmod 7$ : $5^6 \equiv 1$ , and $100 = 6 \cdot 16 + 4$ , so $5^{100} \equiv 5^4 = 625 \equiv 2 \pmod 7$ .

Euler's theorem

For a modulus that isn't prime, you need to know how many residues are invertible.

Definition

Euler's totient function

$\varphi(n)$ is the number of integers in $\{1, 2, \dots, n\}$ that are relatively prime to $n$ . If $n = p_1^{e_1} p_2^{e_2} \cdots p_k^{e_k}$ , then

$\varphi(n) = n\left(1 - \frac{1}{p_1}\right)\left(1 - \frac{1}{p_2}\right)\cdots\left(1 - \frac{1}{p_k}\right) = \prod p_i^{e_i - 1}(p_i - 1).$

For a prime power, $\varphi(p^e) = p^e - p^{e-1}$ : out of $p^e$ numbers, the multiples of $p$ are the only ones that fail. For general $n$ , $\varphi$ is multiplicative: $\varphi(mn) = \varphi(m)\varphi(n)$ when $\gcd(m, n) = 1$ . That follows from the Chinese remainder theorem (next module): a residue mod $mn$ is coprime to $mn$ exactly when its residues mod $m$ and mod $n$ are coprime to $m$ and $n$ . Useful values: $\varphi(100) = 40$ , $\varphi(125) = 100$ , $\varphi(1000) = 400$ .

Euler's theorem

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

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

The proof is the same as Fermat's. Let $r_1, \dots, r_{\varphi(n)}$ be the residues coprime to $n$ . Multiplying each by $a$ permutes them (same cancellation argument), so $a^{\varphi(n)} \prod r_i \equiv \prod r_i$ , and the product is invertible mod $n$ . Fermat is the special case $n = p$ , $\varphi(p) = p - 1$ .

Common mistake

Euler's theorem needs $\gcd(a, n) = 1$ . For $2^{2026} \bmod 1000$ you cannot reduce the exponent mod $400$ , because $\gcd(2, 1000) \ne 1$ . Split $1000 = 8 \cdot 125$ instead: $2^{2026} \equiv 0 \pmod 8$ , and Euler works mod $125$ . Then combine with the Chinese remainder theorem.

Also, $\varphi(n)$ is a period, not necessarily the smallest period. Mod $1000$ , $7^{20} \equiv 1$ already, even though $\varphi(1000) = 400$ . Finding the smallest period is the subject of the module on orders.

Wilson's theorem

If $p$ is prime, then $(p-1)! \equiv -1 \pmod p$ .

Why. Each of $1, 2, \dots, p-1$ has an inverse mod $p$ . The only numbers that are their own inverse satisfy $x^2 \equiv 1$ , that is, $p \mid (x-1)(x+1)$ , so $x \equiv \pm 1$ . All the other factors in $(p-1)!$ pair off with their inverses, and each pair multiplies to $1$ . What's left is $1 \cdot (p-1) \equiv -1$ .

Wilson's theorem is how you handle factorials mod a prime: $(p-2)! \equiv 1$ , and in general you peel off the top few factors, which are $\equiv -1, -2, -3, \dots$ .

Worked examples

Worked example: Last two digits

Find the last two digits of $3^{2026}$ .

Since $\gcd(3, 100) = 1$ and $\varphi(100) = 40$ , you have $3^{40} \equiv 1 \pmod{100}$ . Now $2026 = 40 \cdot 50 + 26$ , so $3^{2026} \equiv 3^{26}$ .

Compute: $3^{10} = 59049 \equiv 49$ , so $3^{20} \equiv 49^2 = 2401 \equiv 1 \pmod{100}$ . (The true period is $20$ , even better.) Then $3^{26} \equiv 3^6 = 729 \equiv 29$ .

The last two digits are $29$ .

Worked example: A tower

Find the remainder when $2^{3^{2026}}$ is divided by $11$ .

Mod $11$ , $2^{10} \equiv 1$ , so you only need the exponent $3^{2026}$ mod $10$ . Powers of $3$ mod $10$ cycle $3, 9, 7, 1$ with period $4$ , and $2026 \equiv 2 \pmod 4$ , so $3^{2026} \equiv 9 \pmod{10}$ .

So $2^{3^{2026}} \equiv 2^9 = 512 = 11 \cdot 46 + 6$ . The remainder is $6$ .

The pattern for towers: to reduce $a^{b^c}$ mod $n$ , reduce the exponent $b^c$ mod $\varphi(n)$ (or a smaller period), which is again a power problem with a smaller modulus.

Worked example: Wilson's theorem

Find the remainder when $99!$ is divided by $101$ .

By Wilson, $100! \equiv -1 \pmod{101}$ . But $100! = 99! \cdot 100$ and $100 \equiv -1$ , so $-99! \equiv -1$ , giving $99! \equiv 1$ . The remainder is $1$ .

Worked example: A divisibility for all n

Prove that $n^7 - n$ is divisible by $42$ for every integer $n$ .

$42 = 2 \cdot 3 \cdot 7$ . By Fermat, $n^7 \equiv n \pmod 7$ . Mod $3$ : $n^3 \equiv n$ , so $n^7 = n^3 \cdot n^3 \cdot n \equiv n \cdot n \cdot n = n^3 \equiv n$ . Mod $2$ : $n^7$ and $n$ have the same parity. So $2$ , $3$ and $7$ all divide $n^7 - n$ , and so does their product.

In general, $p \mid n^k - n$ for all $n$ whenever $(p-1) \mid (k-1)$ .

Tip

Mod $1000$ , always split into mod $8$ and mod $125$ . Powers of $2$ die mod $8$ quickly, and mod $125$ you have $\varphi(125) = 100$ , so exponents reduce mod $100$ .