Modular arithmetic | AMC Number theory

This chapter applies to all AMC 8/10/12 test takers.

Modular arithmetic is about remainders in division. For example, when you divide $29$ by $5$ , the remainder is $4$ . We write that as $29 \equiv 4 (mod 5)$ .

The word “modular” comes from the Latin modulus, meaning a small measure. So $29 \equiv 4 (mod 5)$ is like saying: “If you measure $29$ in chunks of $5$ , you have $4$ left over.”

$a \equiv b (mod n)$

The triple-bar equals sign means “congruent modulo.” The statement above reads: “ $a$ is congruent to $b$ modulo $n$ .” In practical terms, it means $a$ and $b$ leave the same remainder when divided by $n$ .

Modular properties

Even though $\equiv$ is not the same as $=$ , you can still do many familiar algebra-like operations with congruences.

Here are three useful properties. For all three, assume:

$a \equiv b (mod n)$
$c \equiv d (mod n)$

In the examples, we’ll use $a = 9$ , $b = 4$ , $c = 7$ , $d = 2$ , and $n = 5$ , so:

$9 \equiv 4 (mod 5)$ and $7 \equiv 2 (mod 5)$

A key theme is that the modulus (the number after “mod”) must match. When two congruences share the same modulus, you can combine them using the operations below.

Addition

$a + c \equiv b + d (mod n)$

When $a \equiv b (mod 5)$ and $c \equiv d (mod 5)$ , $a + c \equiv b + d (mod 5)$

if $9 \equiv 4 (mod 5)$ and $7 \equiv 2 (mod 5)$

then $9 + 7 \equiv 4 + 2 (mod 5)$

$16 \equiv 6 (mod 5)$

$16 \equiv 1 (mod 5)$

That last step is important. The number on the right side of $\equiv$ is representing a remainder, so it should be written as a number less than the modulus. Since $6$ is $1$ more than $5$ , we replace $6$ with $1$ .

Subtraction

$a - c \equiv b - d (mod n)$

When $a \equiv b (mod 5)$ and $c \equiv d (mod 5)$ , $a - c \equiv b - d (mod 5)$

if $9 \equiv 4 (mod 5)$ and $7 \equiv 2 (mod 5)$

then $9 - 7 \equiv 4 - 2 (mod 5)$

$2 \equiv 2 (mod 5)$

Here, $2$ is already less than $5$ , so no further simplification is needed.

This connects to a basic fact you’ll use often: $x \equiv x (mod y)$ when $y > x$ .

Multiplication

$a \cdot c \equiv b \cdot d (mod n)$

When $a \equiv b (mod 5)$ and $c \equiv d (mod 5)$ , $a \cdot c \equiv b \cdot d (mod 5)$

if $9 \equiv 4 (mod 5)$ and $7 \equiv 2 (mod 5)$

then $9 \cdot 7 \equiv 4 \cdot 2 (mod 5)$

$63 \equiv 8 (mod 5)$

$63 \equiv 3 (mod 5)$

Again, we reduce the right-hand side to a remainder less than $5$ : since $8 \equiv 3 (mod 5)$ , we write $63 \equiv 3 (mod 5)$ .

Fermat’s little theorem

$a^{p - 1} \equiv 1 (mod p)$

Here, $p$ is any prime number, and $a$ is a positive integer.

The theorem applies when $p$ is prime and $a$ is not a multiple of $p$ .
It says that if you raise $a$ to the power $p - 1$ and divide by $p$ , the remainder is $1$ .

Example: The question below is from 2017 AMC 10B

An integer $N$ is selected at random in the range $1 \leq N \leq 2020$ . What is the probability that the remainder when $N^{16}$ is divided by $5$ is $1$ ?
a. $\frac{1}{5}$
b. $\frac{2}{5}$
c. $\frac{3}{5}$
d. $\frac{4}{5}$
e. $1$

(spoiler)

Answer: D. $\frac{4}{5}$

Notice that $N^{16}$ can be rewritten as $(N^{4})^{4}$ . To connect this to Fermat’s little theorem, set $p = 5$ , so the exponent $p - 1$ is $4$ . That’s why $N^{4}$ is the key piece to analyze modulo $5$ .

Euler’s theorem

$a^{ϕ (n)} \equiv 1 (mod n)$

Euler’s theorem is a generalization of Fermat’s little theorem.

For the theorem to apply, $a$ and $n$ must be coprime (they share no prime factors).
$ϕ (n)$ is Euler’s totient function: it counts how many positive integers less than $n$ are coprime to $n$ .

For example, $ϕ (10) = 4$ because there are $4$ numbers less than $10$ that are coprime to $10$ : $1$ , $3$ , $7$ , and $9$ .

Plugging in one of these coprimes gives:

$7^{4} \equiv 1 (mod 10)$

In other words, the remainder of $2401$ when divided by $10$ is $1$ .

Example: The question below is from 2024 AMC 10B

How many different remainders can result when the $100$ th power of an integer is divided by $125$ ?
a. $1$
b. $2$
c. $5$
d. $25$
e. $125$

(spoiler)

Answer: B. $2$

Common themes

Any number mod $10$ is just the last digit of the original number.
You can quickly determine if a number is $0 (mod x)$ if $x$ is a factor of the original number.
Try the first few smaller exponents and look for a cycle, or repetition, in modular arithmetic questions that involve larger exponents.
Questions that involve clocks will likely involve the use of mod $12$ (for each hour) or mod $60$ (for each minute).

This chapter applies to all AMC 8/10/12 test takers.

Modular arithmetic is about remainders in division. For example, when you divide $29$ by $5$ , the remainder is $4$ . We write that as $29 \equiv 4 (mod 5)$ .

The word “modular” comes from the Latin modulus, meaning a small measure. So $29 \equiv 4 (mod 5)$ is like saying: “If you measure $29$ in chunks of $5$ , you have $4$ left over.”

$a \equiv b (mod n)$

Modular properties

Even though $\equiv$ is not the same as $=$ , you can still do many familiar algebra-like operations with congruences.

Here are three useful properties. For all three, assume:

$a \equiv b (mod n)$
$c \equiv d (mod n)$

In the examples, we’ll use $a = 9$ , $b = 4$ , $c = 7$ , $d = 2$ , and $n = 5$ , so:

$9 \equiv 4 (mod 5)$ and $7 \equiv 2 (mod 5)$

A key theme is that the modulus (the number after “mod”) must match. When two congruences share the same modulus, you can combine them using the operations below.

Addition

$a + c \equiv b + d (mod n)$

When $a \equiv b (mod 5)$ and $c \equiv d (mod 5)$ , $a + c \equiv b + d (mod 5)$

if $9 \equiv 4 (mod 5)$ and $7 \equiv 2 (mod 5)$

then $9 + 7 \equiv 4 + 2 (mod 5)$

$16 \equiv 6 (mod 5)$

$16 \equiv 1 (mod 5)$

Subtraction

$a - c \equiv b - d (mod n)$

When $a \equiv b (mod 5)$ and $c \equiv d (mod 5)$ , $a - c \equiv b - d (mod 5)$

if $9 \equiv 4 (mod 5)$ and $7 \equiv 2 (mod 5)$

then $9 - 7 \equiv 4 - 2 (mod 5)$

$2 \equiv 2 (mod 5)$

Here, $2$ is already less than $5$ , so no further simplification is needed.

This connects to a basic fact you’ll use often: $x \equiv x (mod y)$ when $y > x$ .

Multiplication

$a \cdot c \equiv b \cdot d (mod n)$

When $a \equiv b (mod 5)$ and $c \equiv d (mod 5)$ , $a \cdot c \equiv b \cdot d (mod 5)$

if $9 \equiv 4 (mod 5)$ and $7 \equiv 2 (mod 5)$

then $9 \cdot 7 \equiv 4 \cdot 2 (mod 5)$

$63 \equiv 8 (mod 5)$

$63 \equiv 3 (mod 5)$

Again, we reduce the right-hand side to a remainder less than $5$ : since $8 \equiv 3 (mod 5)$ , we write $63 \equiv 3 (mod 5)$ .

Fermat’s little theorem

$a^{p - 1} \equiv 1 (mod p)$

Here, $p$ is any prime number, and $a$ is a positive integer.

The theorem applies when $p$ is prime and $a$ is not a multiple of $p$ .
It says that if you raise $a$ to the power $p - 1$ and divide by $p$ , the remainder is $1$ .

Example: The question below is from 2017 AMC 10B

An integer $N$ is selected at random in the range $1 \leq N \leq 2020$ . What is the probability that the remainder when $N^{16}$ is divided by $5$ is $1$ ?
a. $\frac{1}{5}$
b. $\frac{2}{5}$
c. $\frac{3}{5}$
d. $\frac{4}{5}$
e. $1$

(spoiler)

Answer: D. $\frac{4}{5}$

Euler’s theorem

$a^{ϕ (n)} \equiv 1 (mod n)$

Euler’s theorem is a generalization of Fermat’s little theorem.

For the theorem to apply, $a$ and $n$ must be coprime (they share no prime factors).
$ϕ (n)$ is Euler’s totient function: it counts how many positive integers less than $n$ are coprime to $n$ .

For example, $ϕ (10) = 4$ because there are $4$ numbers less than $10$ that are coprime to $10$ : $1$ , $3$ , $7$ , and $9$ .

Plugging in one of these coprimes gives:

$7^{4} \equiv 1 (mod 10)$

In other words, the remainder of $2401$ when divided by $10$ is $1$ .

Example: The question below is from 2024 AMC 10B

How many different remainders can result when the $100$ th power of an integer is divided by $125$ ?
a. $1$
b. $2$
c. $5$
d. $25$
e. $125$

(spoiler)

Answer: B. $2$

Common themes

Any number mod $10$ is just the last digit of the original number.
You can quickly determine if a number is $0 (mod x)$ if $x$ is a factor of the original number.
Try the first few smaller exponents and look for a cycle, or repetition, in modular arithmetic questions that involve larger exponents.
Questions that involve clocks will likely involve the use of mod $12$ (for each hour) or mod $60$ (for each minute).