Printable problems

Modular Arithmetic

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

Print without answers Back to the topic

Modular ArithmeticAMC 10 Step by Step

Name: Date: October 28, 2026

18 problems, easiest first

What you need to know

What "mod" means. $a \equiv b \pmod m$ means $a$ and $b$ leave the same remainder when divided by $m$ ; in other words, $m$ divides $a-b$ . Example: $17 \equiv 2 \pmod 5$ , since $5$ divides $15$ .
Working with remainders. You can add, subtract, and multiply congruences, swapping any number for its remainder. You may divide both sides by $c$ only when $c$ shares no factor with $m$ . Example: $17\cdot23 \equiv 2\cdot3 = 6 \equiv 1 \pmod 5$ . But $6 \equiv 16 \pmod{10}$ while $3 \not\equiv 8 \pmod{10}$ : dividing by $2$ failed.
Units digits cycle. The units digits of $a, a^2, a^3, \dots$ repeat with a cycle length that divides $4$ . Example: powers of $2$ end in $2, 4, 8, 6, \dots$ ; since $2026 = 4\cdot506+2$ , $2^{2026}$ ends in $4$ .
Any modulus. The remainders of $a^n$ mod $m$ always start repeating at some point, so once inside the cycle, reduce the exponent by the cycle length. A few powers may come before the cycle starts. Example: mod $12$ , powers of $2$ go $2, 4, 8, 4, 8, \dots$ ; the cycle starts at $2^2$ .
Fermat's Little Theorem. If $p$ is prime and does not divide $a$ , then $a^{p-1} \equiv 1 \pmod p$ .
Squares. A square leaves remainder $0$ or $1$ when divided by $3$ or by $4$ . Divided by $8$ , a square leaves $0$ , $1$ , or $4$ , and an odd square always leaves $1$ . Example: $49 = 8\cdot6+1$ and $36 = 8\cdot4+4$ .
Chinese Remainder Theorem. If $\gcd(m,n) = 1$ , a number's remainders mod $m$ and mod $n$ pin down its remainder mod $mn$ . Example: remainder $2$ mod $3$ and $3$ mod $5$ means remainder $8$ mod $15$ .
Digit shortcuts. A number and its digit sum agree mod $9$ . Mod $11$ , use the alternating digit sum, starting with $+$ on the units digit. Mod $100$ , keep the last two digits. Example: $2026$ leaves $1$ mod $9$ (digit sum $10$ ), $2$ mod $11$ ( $6-2+0-2$ ), and $26$ mod $100$ .

How AMC 10 tests it

"What is the units digit (or remainder mod $7$ ) of $3^{2026}+\ldots$ ?" Find the cycle and 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$ ": the Chinese Remainder Theorem, by listing or stepping through multiples (problems 12–20).
Showing an equation has no solutions by working mod $3$ , $4$ , $8$ , or $9$ .
Divisibility in disguise, such as "the average was a whole number after each entry," which means the first $k$ entries add up to a multiple of $k$ .

Standard approaches

Reduce the base first, find the cycle length of its powers, and reduce the exponent by that length (never by $m$ ).
In sums of factorials or products, every term past some point is $\equiv 0$ , so only the first few matter. Example: from $5!$ on, factorials end in $0$ , so $1!+2!+\dots+100!$ ends in the same digit as $1+2+6+24 = 33$ .
For several congruences, start with the largest modulus and step through its numbers until the others hold. Example: above, $n \equiv 1 \pmod 7$ gives $1, 8, \dots$ , and $8$ already works.
For "no integer solutions," use a modulus where squares or cubes have few remainders. Example: $x^2+y^2$ leaves $0$ , $1$ , or $2$ mod $4$ , so it never equals $2027$ .
Use negative remainders to make powers easy: $10 \equiv -1 \pmod{11}$ , so $10^{2026} \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$

Step 1: the cycle. Multiply by $3$ and keep the remainder mod $7$ each time: $3^1 \equiv 3$ , $3^2 \equiv 2$ , $3^3 \equiv 6$ , $3^4 \equiv 4$ , $3^5 \equiv 5$ , $3^6 \equiv 1$ . The pattern $3, 2, 6, 4, 5, 1$ repeats every $6$ powers.

Step 2: place $3^{2026}$ . $2026 = 6\cdot337+4$ , so $3^{2026} \equiv 3^4 \equiv 4 \pmod 7$ .

Step 3: add. $2026 = 7\cdot289+3$ , so $2026 \equiv 3$ . Then $3^{2026}+2026 \equiv 4+3 = 7 \equiv 0 \pmod 7$ .

The answer is $\boxed{\textbf{(A)}\ 0}$ .

Pitfalls

Reducing the exponent by $m$ instead of the cycle length. Example: using $2026 \equiv 3 \pmod 7$ gives $3^3 \equiv 6$ , which is wrong.
Misplacing remainder $0$ : it means the end of the cycle. Example: $2028 = 6\cdot338$ , so $3^{2028}$ is the $6$ th entry, $1$ , not the first entry, $3$ . Likewise $2^{2028}$ ends in $6$ , the last of $2, 4, 8, 6$ , not in $2^0 = 1$ .
Dividing both sides by a number that shares a factor with the modulus (see the $6 \equiv 16$ example above).
Off-by-one errors in calendar problems: counting the starting day, or February in leap years. Example: $10$ days after a Monday is a Thursday ( $10 = 7+3$ ), not a Wednesday.

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)

1.2010 AMC 10B #18
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$ ?
1. A) $\dfrac{1}{3}$
2. B) $\dfrac{29}{81}$
3. C) $\dfrac{31}{81}$
4. D) $\dfrac{11}{27}$
5. E) $\dfrac{13}{27}$
2.2009 AMC 10B #21
What is the remainder when $3^0 + 3^1 + 3^2 + \cdots + 3^{2009}$ is divided by 8?
1. A) $0$
2. B) $1$
3. C) $2$
4. D) $4$
5. E) $6$
3.2006 AMC 10A #20
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$ ?
1. A) $\frac{1}{2}$
2. B) $\frac{3}{5}$
3. C) $\frac{2}{3}$
4. D) $\frac{4}{5}$
5. E) $1$
4.2004 AMC 10B #13
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?
1. A) $7$
2. B) $8$
3. C) $9$
4. D) $10$
5. E) $11$
5.2000 AMC 10 #14
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) were $71$ , $76$ , $80$ , $82$ , and $91$ . What was the last score Mrs. Walters entered?
1. A) $71$
2. B) $76$
3. C) $80$
4. D) $82$
5. E) $91$
6.2000 AMC 10 #17
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 repeatedly?
1. A)$3.63
2. B)$5.13
3. C)$6.30
4. D)$7.45
5. E)$9.07
7.2024 AMC 10B #24
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?
1. A) $0$
2. B) $1$
3. C) $2$
4. D) $3$
5. E) $4$
8.2024 AMC 10B #18
How many different remainders can result when the $100$ th power of an integer is divided by $125$ ?
1. A) $1$
2. B) $2$
3. C) $5$
4. D) $25$
5. E) $125$
9.2022 AMC 10A #19
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$ ?
1. A) $1$
2. B) $3$
3. C) $5$
4. D) $7$
5. E) $9$
10.2021 AMC Fall 10B #22
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$ ?
1. A) $196$
2. B) $197$
3. C) $198$
4. D) $199$
5. E) $200$
11.2017 AMC 10B #23
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$ ?
1. A) $1$
2. B) $4$
3. C) $9$
4. D) $18$
5. E) $44$
12.2017 AMC 10B #25
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?
1. A) $92$
2. B) $94$
3. C) $96$
4. D) $98$
5. E) $100$
13.2011 AMC 10B #23
What is the hundreds digit of $2011^{2011}$ ?
1. A) $1$
2. B) $4$
3. C) $5$
4. D) $6$
5. E) $9$
14.2008 AMC 10A #24
Let $k={2008}^{2}+{2}^{2008}$ . What is the units digit of $k^2+2^k$ ?
1. A) $0$
2. B) $2$
3. C) $4$
4. D) $6$
5. E) $8$
15.2003 AMC 10A #25
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$ ?
1. A) $8180$
2. B) $8181$
3. C) $8182$
4. D) $9000$
5. E) $9090$
16.2003 AMC 10B #25
How many distinct four-digit numbers are divisible by $3$ and have $23$ as their last two digits?
1. A) $27$
2. B) $30$
3. C) $33$
4. D) $81$
5. E) $90$
17.2022 AMC 10B #25
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}?$
1. A) $6$
2. B) $7$
3. C) $12$
4. D) $14$
5. E) $15$
18.2010 AMC 10A #24
The number obtained from the last two nonzero digits of $90!$ is equal to $n$ . What is $n$ ?
1. A) $12$
2. B) $32$
3. C) $48$
4. D) $52$
5. E) $68$

Modular Arithmetic — answersAMC 10 Step by Step

Name: Date: October 28, 2026

Keep this page separate from the problems.

Answers

#	Answer	The idea it turns on
1	E	Factor the expression as a times (bc + b + 1). It is a multiple of 3 when a is, or when bc + b + 1 is.
2	D	Divided by 8, powers of 3 leave remainders 1, 3, 1, 3, and so on. Each pair adds to 4, and there are 1005 pairs.
3	E	Two numbers differ by a multiple of 5 exactly when they leave the same remainder when divided by 5. Six numbers but only five remainders, so it always happens.
4	B	In hundredths of a millimeter, every coin is 15 more than a multiple of 20. So the coin count must be a multiple of 4: 8.
5	C	A whole-number average means the first k scores add to a multiple of k. Work backward from the total 400, using multiples of 4 and then multiples of 3.
6	D	Trading a quarter or a nickel keeps the money the same. Trading a penny adds exactly 124 cents. So any total is 1 cent more than a multiple of 124.
7	E	Put everything over 8. For even m each top term is a multiple of 8. For odd m the top becomes 4(m + 1), a multiple of 8.
8	B	Multiples of 5 give remainder 0. Any other number to the 100th power is 1 more than a multiple of 125, built up one factor of 5 at a time.
9	C	Multiply through by L17. Then h is L17/1 + L17/2 + ... + L17/17, and every term except the last is a multiple of 17.
10	B	Squaring 1 + 2 + ... + n gives each product twice, leading to a formula with 24 on the bottom. So the top needs a factor of 9.
11	C	Split 45 into 5 and 9. N ends in 4, so its remainder by 5 is 4; its digit sum matches 1 through 44 added up, 990.
12	E	Subtract 90 from each score. The 7-test total is a multiple of 7 from 28 to 49, and minus 5 it must be a multiple of 6: only 35.
13	D	Only the last three digits matter, and they match those of 11 to the 2011th power. For 11 to the n, they come from 1 + 10n + 50n(n-1).
14	D	k and its square end in 0. Powers of 2 end in 2, 4, 8, 6 repeating. Since k is a multiple of 4, 2^k ends in 6.
15	B	Write n as 99 times q plus the sum q + r. Since 11 divides 99, q + r is a multiple of 11 exactly when n is.
16	B	The 90 numbers 1023, 1123, ..., 9923 go up by 100. Each step changes the remainder after dividing by 3, so every third number works.
17	A	Write the first few S_n in binary. After the first 1 the bits repeat 1, 1, 0, so bits at multiples of 3 are 0.
18	A	Remove the 21 fives and 21 twos that make the zeros, then track only the remainder after dividing by 25. Runs of four non-multiples of 5 act like -1.

Problems © Mathematical Association of America (MAA), American Mathematics Competitions. Reproduced for non-commercial educational use. The topic note, tags and key insights are original to this site.