Topics / Number Theory

Modular Arithmetic

Remainders, congruences, last digits, cyclicity, Chinese-remainder style reasoning

Modular ArithmeticAMC 10 Step by Step

Name: Date: September 13, 2026

Number Theory · 38 problems have this as their main idea

primary-topic problems (2.9% of all)

What you need to know

$a \equiv b \pmod m$ means $m \mid (a - b)$ . Congruences can be added, subtracted, and multiplied; you may divide by $c$ only when $\gcd(c, m) = 1$ .
Powers cycle: the units digits of $a^n$ repeat with period dividing $4$ ; in general $a^n \bmod m$ is eventually periodic, so reduce the exponent modulo the period.
Fermat's little theorem: if $p$ is prime and $p \nmid a$ , then $a^{p-1} \equiv 1 \pmod p$ .
Squares are $\equiv 0, 1 \pmod 3$ and $\pmod 4$ ; every square is $\equiv 0, 1, 4 \pmod 8$ , and every odd square is $\equiv 1 \pmod 8$ .
Chinese Remainder Theorem: if $\gcd(m, n) = 1$ , a residue mod $m$ and a residue mod $n$ determine a unique residue mod $mn$ .
$n \equiv (\text{digit sum}) \pmod 9$ ; $n \equiv (\text{alternating digit sum}) \pmod{11}$ ; $n \bmod 100$ is the last two digits.

How AMC 10 tests it

"What is the units digit (or remainder mod $7$ ) of $3^{2026} + \ldots$ ?" Find the cycle, reduce the exponent (problems 8–15).
Day-of-week or clock problems: count days, reduce mod $7$ or $12$ , watch leap years.
"Find the smallest $n$ with $n \equiv 2 \pmod 3$ , $n \equiv 3 \pmod 5$ , $n \equiv 1 \pmod 7$ ": CRT by listing or by stepping through multiples (problems 12–20).
Impossibility proofs: show an equation has no solutions by reducing mod $3$ , $4$ , $8$ , or $9$ .
Disguised divisibility, such as "the average was an integer after each entry" meaning partial sums are divisible by their length.

Standard approaches

Reduce the base first, then find the period of the powers and reduce the exponent modulo that period (never modulo $m$ ).
For sums of factorials or products, note that all terms beyond a point are $\equiv 0$ ; only the first few matter.
For simultaneous congruences, satisfy the largest modulus, then step by it until the next condition holds.
For "no integer solutions," pick a modulus where squares or cubes take few values.
Use negative residues ( $-1$ instead of $m - 1$ ) to make powers trivial: $10 \equiv -1 \pmod{11}$ .

Worked example

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

(A) $0$ (B) $1$ (C) $3$ (D) $4$ (E) $6$

Powers of $3$ modulo $7$ : $3, 2, 6, 4, 5, 1$ , then repeat with period $6$ . Since $2026 = 6 \cdot 337 + 4$ , we have $3^{2026} \equiv 3^4 \equiv 4 \pmod 7$ . Next, $2026 = 7 \cdot 289 + 3$ , so $2026 \equiv 3 \pmod 7$ . Adding, $3^{2026} + 2026 \equiv 4 + 3 = 7 \equiv 0 \pmod 7$ . The answer is $\boxed{\textbf{(A)}\ 0}$ .

Pitfalls

Reducing the exponent modulo $m$ instead of modulo the period of the cycle.
Treating remainder $0$ as "cycle position $0$ ": $3^{2028}$ corresponds to position $6$ , i.e., $3^6 \equiv 1$ , not $3^0$ .
Dividing both sides of a congruence by a number sharing a factor with the modulus.
Off-by-one errors in calendar problems (counting the starting day, February in leap years).

Traps that recur

Assuming the bits repeat 111 or 011 from the first few (x₀ = x₁ = x₂ = 1) without computing far enough to see the period-3 pattern 0,1,1. (2022 AMC 10B #25)
Reducing 90! mod 100 directly (it is 0) or forgetting that removing 21 factors of 5 also requires removing exactly 21 factors of 2. (2010 AMC 10A #24)
Assuming powers spread out over many residues (answering 25 or 125) instead of testing whether 100 is a multiple of the order of every unit mod 125. (2024 AMC 10B #18)
Testing only whether each fraction is an integer separately; for odd m none of them is, yet the fractional parts 1/2 + 1/4 + 1/8 + 1/8 add up to exactly 1. (2024 AMC 10B #24)

Problems, easiest first

2023 AMC 10B · #8Modular Arithmetic

What is the units digit of $2022^{2023} + 2023^{2022}$ ?

2012 AMC 10B · #4Modular Arithmetic

When Ringo places his marbles into bags with 6 marbles per bag, he has 4 marbles left over. When Paul does the same with his marbles, he has 3 marbles left over. Ringo and Paul pool their marbles and place them into as many bags as possible, with 6 marbles per bag. How many marbles will be left over?

2025 AMC 10B · #2Modular Arithmetic

Jerry wrote down the ones digit of each of the first $2025$ positive squares: $1,4,9,6,5,6,\dots$ . What is the sum of all the numbers Jerry wrote down?

2024 AMC 10B · #7Modular Arithmetic

What is the remainder when $7^{2024}+7^{2025}+7^{2026}$ is divided by $19$ ?

2023 AMC 10B · #6Modular Arithmetic

Let $L_1 = 1$ , $L_2 = 3$ , and $L_{n+2} = L_{n+1}+L_n$ for $n \geq 1$ . How many terms in the sequence $L_1, L_2, L_3, \cdots, L_{2023}$ are even?

2021 AMC Fall 10A · #12Modular Arithmetic

The base-nine representation of the number $N$ is $27{,}006{,}000{,}052_{\text{nine}}.$ What is the remainder when $N$ is divided by $5?$

2017 AMC 10A · #13Modular Arithmetic

Define a sequence recursively by $F_{0}=0,~F_{1}=1,$ and $F_{n}=$ the remainder when $F_{n-1}+F_{n-2}$ is divided by $3,$ for all $n\geq 2.$ Thus the sequence starts $0,1,1,2,0,2,\ldots$ What is $F_{2017}+F_{2018}+F_{2019}+F_{2020}+F_{2021}+F_{2022}+F_{2023}+F_{2024}?$

2016 AMC 10B · #8Modular Arithmetic

What is the tens digit of $2015^{2016}-2017?$

2015 AMC 10B · #10Modular Arithmetic

What is the sign and units digit of the product of all the odd negative integers strictly greater than $-2015$ ?

2009 AMC 10B · #13Modular Arithmetic

As shown below, convex pentagon $ABCDE$ has sides $AB=3$ , $BC=4$ , $CD=6$ , $DE=3$ , and $EA=7$ . The pentagon is originally positioned in the plane with vertex $A$ at the origin and vertex $B$ on the positive $x$ -axis. The pentagon is then rolled clockwise to the right along the $x$ -axis. Which side will touch the …

2007 AMC 10B · #9Modular Arithmetic

A cryptographic code is designed as follows. The first time a letter appears in a given message it is replaced by the letter that is $1$ place to its right in the alphabet (asumming that the letter $A$ is one place to the right of the letter $Z$ ). The second time this same letter appears in the given message, it is …

2006 AMC 10B · #11Modular Arithmetic

What is the tens digit in the sum $7!+8!+9!+...+2006!$

2003 AMC 10A · #16Modular Arithmetic

What is the units digit of $13^{2003}$ ?

2000 AMC 10 · #6Modular Arithmetic

The Fibonacci sequence $1,1,2,3,5,8,13,21,\ldots$ starts with two 1s, and each term afterwards is the sum of its two predecessors. Which one of the ten digits is the last to appear in the units position of a number in the Fibonacci sequence?

2022 AMC 10B · #17Modular Arithmetic

One of the following numbers is not divisible by any prime number less than $10.$ Which is it?

2020 AMC 10B · #15Modular Arithmetic

Steve wrote the digits $1$ , $2$ , $3$ , $4$ , and $5$ in order repeatedly from left to right, forming a list of $10,000$ digits, beginning $123451234512\ldots.$ He then erased every third digit from his list (that is, the $3$ rd, $6$ th, $9$ th, $\ldots$ digits from the left), then erased every fourth digit from the …

2018 AMC 10B · #16Modular Arithmetic

Let $a_1,a_2,\dots,a_{2018}$ be a strictly increasing sequence of positive integers such that $a_1+a_2+\cdots+a_{2018}=2018^{2018}.$ What is the remainder when $a_1^3+a_2^3+\cdots+a_{2018}^3$ is divided by $6$ ?

2018 AMC 10B · #13Modular Arithmetic

How many of the first $2018$ numbers in the sequence $101, 1001, 10001, 100001, \dots$ are divisible by $101$ ?

2018 AMC 10A · #19Modular Arithmetic

A number $m$ is randomly selected from the set $\{11,13,15,17,19\}$ , and a number $n$ is randomly selected from $\{1999,2000,2001,\ldots,2018\}$ . What is the probability that $m^n$ has a units digit of $1$ ?

2017 AMC 10B · #14Modular Arithmetic

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$ ?

2010 AMC 10B · #18Modular Arithmetic

Positive integers $a$ , $b$ , and $c$ are randomly and independently selected with replacement from the set $\{1, 2, 3,\dots, 2010\}$ . What is the probability that $abc + ab + a$ is divisible by $3$ ?

2009 AMC 10B · #21Modular Arithmetic

What is the remainder when $3^0 + 3^1 + 3^2 + \cdots + 3^{2009}$ is divided by 8?

2006 AMC 10A · #20Modular Arithmetic

Six distinct positive integers are randomly chosen between $1$ and $2006$ , inclusive. What is the probability that some pair of these integers has a difference that is a multiple of $5$ ?

2004 AMC 10B · #13Modular Arithmetic

In the United States, coins have the following thicknesses: penny, $1.55$ mm; nickel, $1.95$ mm; dime, $1.35$ mm; quarter, $1.75$ mm. If a stack of these coins is exactly $14$ mm high, how many coins are in the stack?

2000 AMC 10 · #14Modular Arithmetic

Mrs. Walter gave an exam in a mathematics class of five students. She entered the scores in random order into a spreadsheet, which recalculated the class average after each score was entered. Mrs. Walter noticed that after each score was entered, the average was always an integer. The scores (listed in ascending order) …

2000 AMC 10 · #17Modular Arithmetic

Boris has an incredible coin-changing machine. When he puts in a quarter, it returns five nickels; when he puts in a nickel, it returns five pennies; and when he puts in a penny, it returns five quarters. Boris starts with just one penny. Which of the following amounts could Boris have after using the machine …

2024 AMC 10B · #18Modular Arithmetic

How many different remainders can result when the $100$ th power of an integer is divided by $125$ ?

2024 AMC 10B · #24Modular Arithmetic

Let $P(m)=\frac{m}{2}+\frac{m^2}{4}+\frac{m^4}{8}+\frac{m^8}{8}$ How many of the values $P(2022)$ , $P(2023)$ , $P(2024)$ , and $P(2025)$ are integers?

2022 AMC 10A · #19Modular Arithmetic

Define $L_n$ as the least common multiple of all the integers from $1$ to $n$ inclusive. There is a unique integer $h$ such that $\frac{1}{1}+\frac{1}{2}+\frac{1}{3}+\cdots+\frac{1}{17}=\frac{h}{L_{17}}$ What is the remainder when $h$ is divided by $17$ ?

2021 AMC Fall 10B · #22Modular Arithmetic

For each integer $n\geq 2$ , let $S_n$ be the sum of all products $jk$ , where $j$ and $k$ are integers and $1\leq j<k\leq n$ . What is the sum of the 10 least values of $n$ such that $S_n$ is divisible by $3$ ?

2017 AMC 10B · #23Modular Arithmetic

Let $N=123456789101112\dots4344$ be the $79$ -digit number that is formed by writing the integers from $1$ to $44$ in order, one after the other. What is the remainder when $N$ is divided by $45$ ?

2017 AMC 10B · #25Modular Arithmetic

Last year Isabella took $7$ math tests and received $7$ different scores, each an integer between $91$ and $100$ , inclusive. After each test she noticed that the average of her test scores was an integer. Her score on the seventh test was $95$ . What was her score on the sixth test?

2011 AMC 10B · #23Modular Arithmetic

What is the hundreds digit of $2011^{2011}$ ?

2008 AMC 10A · #24Modular Arithmetic

Let $k={2008}^{2}+{2}^{2008}$ . What is the units digit of $k^2+2^k$ ?

2003 AMC 10B · #25Modular Arithmetic

How many distinct four-digit numbers are divisible by $3$ and have $23$ as their last two digits?

2003 AMC 10A · #25Modular Arithmetic

Let $n$ be a $5$ -digit number, and let $q$ and $r$ be the quotient and the remainder, respectively, when $n$ is divided by $100$ . For how many values of $n$ is $q+r$ divisible by $11$ ?

2022 AMC 10B · #25Modular Arithmetic

Let $x_0,x_1,x_2,\dotsc$ be a sequence of numbers, where each $x_k$ is either $0$ or $1$ . For each positive integer $n$ , define $S_n = \sum_{k=0}^{n-1} x_k 2^k$ Suppose $7S_n \equiv 1 \pmod{2^n}$ for all $n \geq 1$ . What is the value of the sum $x_{2019} + 2x_{2020} + 4x_{2021} + 8x_{2022}?$

2010 AMC 10A · #24Modular Arithmetic

The number obtained from the last two nonzero digits of $90!$ is equal to $n$ . What is $n$ ?