Math Core

At the AMC 8 level, remainder problems are solved by spotting a repeating pattern. On the AMC 10 and 12 you need more power: congruence notation, division in modular arithmetic, Fermat's little theorem and Euler's theorem for huge exponents, and the Chinese remainder theorem for combining conditions. Together they turn "last two digits of $7^{7^7}$ " into a two-line calculation.

Congruences

Definition

Congruence

$a \equiv b \pmod{m}$ means $m$ divides $a - b$ , so $a$ and $b$ leave the same remainder when divided by $m$ .

Congruences behave like equations for addition, subtraction, multiplication and powers: if $a \equiv b$ and $c \equiv d \pmod{m}$ , then $a + c \equiv b + d$ , $ac \equiv bd$ , and $a^n \equiv b^n \pmod m$ . So you can replace any number by anything congruent to it, at any point. Negative representatives are especially handy: $5 \equiv -1 \pmod 6$ , so $5^{101} \equiv (-1)^{101} = -1 \equiv 5 \pmod 6$ .

Division needs care

You can't always divide. $2 \cdot 3 \equiv 2 \cdot 8 \pmod{10}$ , but $3 \not\equiv 8 \pmod{10}$ . Division by $a$ is allowed exactly when $\gcd(a, m) = 1$ . In that case $a$ has an inverse: a number $a^{-1}$ with $a \cdot a^{-1} \equiv 1 \pmod m$ , and "dividing by $a$ " means multiplying by $a^{-1}$ .

To solve $7x \equiv 5 \pmod{12}$ : since $7 \cdot 7 = 49 \equiv 1$ , the inverse of $7$ is $7$ . Multiply both sides by $7$ : $x \equiv 35 \equiv 11 \pmod{12}$ .

Huge exponents

Fermat and Euler

Fermat's little theorem. If $p$ is prime and $p \nmid a$ , then $a^{p-1} \equiv 1 \pmod p$ .

Euler's theorem. If $\gcd(a, m) = 1$ , then $a^{\varphi(m)} \equiv 1 \pmod m$ , where $\varphi(m)$ counts the integers from $1$ to $m$ that are relatively prime to $m$ . For $m = p_1^{a_1} \cdots p_k^{a_k}$ , $\varphi(m) = m\left(1 - \frac{1}{p_1}\right)\cdots\left(1 - \frac{1}{p_k}\right)$ .

So to reduce $a^n \pmod m$ , reduce the exponent $n$ modulo $\varphi(m)$ (or modulo any smaller cycle length you find).

Why Fermat works: multiplying the nonzero residues $1, 2, \dots, p-1$ by $a$ just rearranges them (no two products can be congruent, since you can cancel $a$ ). So the product of all of them is unchanged: $a^{p-1}(p-1)! \equiv (p-1)! \pmod p$ , and cancelling $(p-1)!$ gives $a^{p-1} \equiv 1$ . Euler's theorem is the same argument using only the residues relatively prime to $m$ .

Useful values: $\varphi(100) = 40$ , $\varphi(1000) = 400$ . The actual cycle is often shorter. For instance $7^4 = 2401 \equiv 1 \pmod{100}$ , and $3^{20} \equiv 1 \pmod{100}$ .

The Chinese remainder theorem

If $m$ and $n$ are relatively prime, then any pair of conditions $x \equiv a \pmod m$ and $x \equiv b \pmod n$ has exactly one solution modulo $mn$ . In practice, you list numbers that satisfy the condition with the largest modulus and test them against the others. The theorem also works in reverse: to find something modulo $1000$ , find it modulo $8$ and modulo $125$ separately and combine.

Worked example: Fermat's little theorem

What is the remainder when $3^{100}$ is divided by $7$ ?

By Fermat, $3^6 \equiv 1 \pmod 7$ . Since $100 = 6 \cdot 16 + 4$ , $3^{100} \equiv 3^4 = 81 \equiv 4 \pmod 7$ . The remainder is $4$ .

Worked example: Last two digits

What are the last two digits of $7^{2026}$ ?

$7^2 = 49$ and $7^4 = 2401 \equiv 1 \pmod{100}$ . Since $2026 = 4 \cdot 506 + 2$ , $7^{2026} \equiv 7^2 = 49 \pmod{100}$ . The last two digits are $49$ .

Worked example: Chinese remainder theorem

What is the smallest positive integer that leaves remainder $2$ when divided by $3$ , remainder $3$ when divided by $5$ , and remainder $4$ when divided by $7$ ?

Numbers that are $4 \pmod 7$ : $4, 11, 18, 25, 32, 39, 46, 53, \dots$ Of these, $18$ and $53$ are $3 \pmod 5$ . Then $18 \equiv 0 \pmod 3$ fails and $53 \equiv 2 \pmod 3$ works. The answer is $53$ , and every solution is $53 + 105k$ .

Worked example: A tower of exponents

What are the last two digits of $7^{7^7}$ ?

Since $7^4 \equiv 1 \pmod{100}$ , you need the exponent $7^7$ modulo $4$ . Because $7 \equiv -1 \pmod 4$ , $7^7 \equiv (-1)^7 \equiv 3 \pmod 4$ . So $7^{7^7} \equiv 7^3 = 343 \equiv 43 \pmod{100}$ . The last two digits are $43$ .

Common mistake

Exponents are reduced modulo the cycle length (like $p - 1$ or $\varphi(m)$ ), never modulo $m$ itself. $2^{10} \bmod 7$ is not $2^3 \bmod 7$ ; since $2^3 \equiv 1 \pmod 7$ , $2^{10} \equiv 2^{1} = 2$ . And Fermat needs $p \nmid a$ : $7^{6} \equiv 0 \pmod 7$ , not $1$ .

Tip

When the modulus is not prime and the base shares a factor with it (like $2^{2026} \bmod 1000$ ), Euler's theorem doesn't apply directly. Split the modulus with the Chinese remainder theorem: the power is $0 \pmod 8$ , and Euler works modulo $125$ .

Practice

Practice 1

What is the remainder when $2^{2026}$ is divided by $7$ ?

Practice 2

For how many integers $n$ with $1 \le n \le 100$ is $n^2 + 1$ divisible by $5$ ?