20. Modular Arithmetic · Mastering AMC 8

20.10%

Modular Arithmetic Fundamentals

In this section you will be able to write remainders as congruences, and use negative remainders when they are easier.

It is 10 o’clock. What time will it be in 5 hours? Not 15 o’clock! The clock wraps around, so it is 3 o’clock.

A clock only remembers the remainder. Modular arithmetic does the same with any number of spots on the dial. When two numbers land on the same spot, you say they are congruent.

Look:a number just below a full lap is a small negative. On a 6-spot dial, 5 is one step before 0, so it is also −1.

Exploreplay first, formulas later

Try this: Press + on a, one click at a time. Where does the pointer go after 5? Why does 6 land back on 0?
Try this: Set a to 23. How many full laps around the dial is that? What spot does it stop on?
Try this: Turn on Negative names. The spot 5 is also called −1. Why is that true for 11, 17 and 23?

Name it

Definition 20.1.1 · Congruence

n \equiv a \pmod{b}

means the number $n$ leaves the same remainder as $a$ when divided by $b$ .

Remark 20.1.2

Mods can also be negative. For example a number that is $5 \pmod{6}$ is also $-1 \pmod{6}$ . This can be useful for simplifying calculations when raising this number to large powers.

Checkpoint for section 20.1

Get 2 of 3 right to master this section. One try each, no hints.

20.20%

Product Rule

In this section you will be able to multiply remainders instead of big numbers, to find last digits and remainders fast.

What is the units digit of 23 × 47? You could multiply it all out. Or you could just multiply 3 × 7 = 21. The answer is 1 either way!

The product rule says you can swap each number for its remainder before you multiply. The last digit of a product depends only on the last digits of the factors.

Look:this works for the last two digits (mod 100) or the last three (mod 1000) too.

Exploreplay first, formulas later

Try this: The dial has 10 spots, so it shows units digits. Is 23 × 47 on the same spot as 3 × 7?
Try this: Change a to 33, then 43. Does the answer spot move? Why not?
Try this: Switch to a + b. Does the same trick work for adding?
Try this: Set mod m to 6. Try a few products. Do the two rows ever land on different spots?

Name it

Theorem 20.2.1 · Product Rule

If $a \equiv x \pmod{n}$ and $b \equiv y \pmod{n}$ , then

ab \equiv xy \pmod{n}

Watch itpredict, then reveal

Example 20.1

AMC 8

If $n$ is an even positive integer, the double factorial notation $n!!$ represents the product of all the even integers from 2 to $n$ . For example, $8!! = 2 \cdot 4 \cdot 6 \cdot 8$ . What is the units digit of the following sum?

2!! + 4!! + 6!! + \cdots + 2018!! + 2020!! + 2022!!

1
Look at $10!! = 2 \cdot 4 \cdot 6 \cdot 8 \cdot 10$ . What is its units digit?

Predict first:
Your prediction

open on YouTube

Example 20.2

AIME

Find the remainder when $9 \times 99 \times 999 \times \cdots \times \underbrace{99\cdots9}_{\text{999 9's}}$ is divided by 1000.

1
The product rule lets you find each term $\pmod{1000}$ and multiply. $9 \equiv 9$ and $99 \equiv 99$ . What is $999 \pmod{1000}$ ? Write it as a negative number.

Predict first:
Your prediction

Contest cornerreal contest problems

Problem 20.6.6

AMC 8

The product of the two 99-digit numbers $303{,}030{,}303{,}\ldots{,}030{,}303$ and $505{,}050{,}505{,}\ldots{,}050{,}505$ has thousands digit $A$ and units digit $B$ . What is the sum of $A$ and $B$ ?

Problem 20.6.13(additional)

AMC 8

If $n$ is an even positive integer, the double factorial notation $n!!$ represents the product of all the even integers from 2 to $n$ . For example, $8!! = 2 \cdot 4 \cdot 6 \cdot 8$ . What is the units digit of the following sum?

2!! + 4!! + 6!! + \cdots + 2018!! + 2020!! + 2022!!

Problem 20.6.14(additional)

MATHCOUNTS

Find the remainder when $1^2 + 2^2 + 3^2 + \cdots + 2016^2$ is divided by 17.

Checkpoint for section 20.2

Get 2 of 3 right to master this section. One try each, no hints.

20.30%

Exponent Rule

In this section you will be able to find remainders of huge powers by swapping the base for a small remainder.

1999 to the power 2000 has more than 6000 digits. You can still find its remainder when divided by 5 in your head!

A power is just the same number multiplied again and again. So the product rule works for powers too: swap the base for its remainder. A remainder of 1 or −1 is the best kind, since its powers are so easy.

Exploreplay first, formulas later

Try this: The base is 1999 and we work mod 5. Press Next power a few times. What pattern do you see?
Try this: 1999 is −1 mod 5. What is (−1) to an even power? To an odd power?
Try this: Press Land k = 2000. Which small power lands on the same spot?

Name it

Theorem 20.3.1 · Exponent Rule

If $a \equiv x \pmod{n}$ , then

a^m \equiv x^m \pmod{n}

Watch itpredict, then reveal

Example 20.3

AMC 8

When $1999^{2000}$ is divided by 5, what is the remainder?

1
What mod value is equivalent to $1999 \pmod{5}$ ?

Predict first:
Your prediction

Example 20.4

Find the remainder of $9^8$ when it's divided by 100.

1
Start small. What is $9^2$ ?

Predict first:
Your prediction

open on YouTube

Contest cornerreal contest problems

Problem 20.6.3

AMC 8

What is the tens digit of $7^{2011}$ ?

Checkpoint for section 20.3

Get 2 of 3 right to master this section. One try each, no hints.

20.40%

Multiple Modular Congruences

In this section you will be able to combine two or more remainder conditions into one.

Sejal has some marbles. In rows of 5, one is left over. In rows of 7, one is left over again. How many marbles could she have?

Each condition is a sieve: it lets through every 3rd, or every 5th, number. Put two sieves together and the survivors are evenly spaced again. The gap is the LCM of the mods.

Look:if every remainder is the same (or the same distance below the divisor), you can subtract it and use the LCM straight away.

Exploreplay first, formulas later

Try this: Turn off the mod 5 condition. Which numbers are 2 mod 3? Now turn it back on. Which numbers survive?
Try this: How far apart are the highlighted numbers? How does that gap relate to 3 and 5?
Try this: Set both remainders to 1, with mods 5 and 7. What one statement mod 35 describes them all?

Name it

Concept 20.4.1 · Combining Mods

We can generally combine different mods together. For example, if $x \equiv 1 \pmod{5}$ and $x \equiv 1 \pmod{7}$ , then $x \equiv 1 \pmod{35}$ .

Watch itpredict, then reveal

Example 20.5

Find the largest possible number less than 100 that leaves a remainder of 1 when divided by 5 and a remainder of 1 when divided by 7.

1
Rewrite the conditions as $x \equiv 1 \pmod{5}$ and $x \equiv 1 \pmod{7}$ . Then what is $x - 1 \pmod{5}$ and $\pmod{7}$ ?

Predict first:
Your prediction

Example 20.6

Find the smallest positive integer that leaves a remainder of 5 when divided by 6, 2 when divided by 5, 2 when divided by 7, and 2 when divided by 11.

1100

1101

1102

1103

1104

1105

1106

1107

1108

1109

1110

1111

1112

1113

1114

1115

1116

1117

1118

1119

1120

1121

1122

1123

1124

1125

1126

1127

1128

1129

1130

1131

1132

1133

1134

1135

1136

1137

1138

1139

1140

1141

1142

1143

1144

1145

1146

1147

1148

1149

1150

1151

1152

1153

1154

1155

1156

1157

1158

1159

1160

1161

1162

1163

1164

1165

1166

1167

1168

1169

1170

1171

1172

1173

1174

1175

1176

1177

1178

1179

1180

1181

1182

1183

1184

1185

1186

1187

1188

1189

1190

1191

1192

1193

1194

1195

1196

1197

1198

1199

1103, 1109, 1115, 1121, 1127, 1133, 1139, …every 6 apart

1
Three conditions share the remainder 2. If $x$ leaves 2 when divided by 5, 7 and 11, what is $x - 2$ a multiple of?

Predict first:
Your prediction

open on YouTube

Try it

Problem 20.6.4

What is the smallest number greater than 2 that leaves a remainder of 2 when divided by 3, 4, 5, or 6?

Problem 20.6.10(additional)

Find the smallest positive number greater than 1 that leaves a remainder of 1 when divided by 2, by 3, by 4, by 5, and by 6.

Contest cornerreal contest problems

Problem 20.6.5

AMC 8

The number $N$ is a two-digit number.

When $N$ is divided by $9$ , the remainder is $1$ .
When $N$ is divided by $10$ , the remainder is $3$ .

What is the remainder when $N$ is divided by $11$ ?

Problem 20.6.7

AMC 8

How many positive three-digit integers have a remainder of 2 when divided by 6, a remainder of 5 when divided by 9, and a remainder of 7 when divided by 11?

Problem 20.6.11(additional)

AMC 8

How many positive integers can fill the blank in the sentence below?

“One positive integer is _____ more than twice another, and the sum of the two numbers is 28.”

Checkpoint for section 20.4

Get 2 of 3 right to master this section. One try each, no hints.

20.50%

Digit Cycles

In this section you will be able to find the last digit of a huge power by spotting the cycle.

What is the last digit of 2 to the power 1026? Nobody wants to multiply 2 by itself 1026 times. Luckily, the last digits repeat!

Each new last digit depends only on the one before it. So once a last digit shows up again, the whole pattern repeats. Find the cycle length, then divide the big exponent by it and use the remainder.

Look:if the remainder is 0, you land on the last spot of the cycle, not the first.

Exploreplay first, formulas later

Try this: Press Next power until a units digit repeats. How long is the cycle for powers of 2?
Try this: Turn on Show the cycle and try base 3, then 7, then 9. Which cycles have length 4? Which have length 2?
Try this: Set mod to 100 to see the last two digits. Is the cycle longer now?

Name it

Concept 20.5.1 · Digit Cycles

To calculate large digit(s) of a number $a^b$ , a strategy that may work is to just look for a pattern by computing the first few values of $a^b$ and then seeing that the pattern will repeat for large values of $b$ .

Watch itpredict, then reveal

Example 20.7

Find the units digit of $2^{1026}$

1
$1026$ is a very large power, so try smaller ones. $2^1, 2^2, 2^3, 2^4$ end in $2, 4, 8, 6$ . What is the units digit of $2^5 = 32$ ?

Predict first:
Your prediction

Example 20.8

Find the remainder when

(15^1 + 15^2 + 15^3 + \cdots + 15^{2022}) + (34^1 + 34^2 + \cdots + 34^{2021})

is divided by 7.

1
What is $15 \pmod{7}$ ? Then what is every $15^k \pmod{7}$ ?

Predict first:
Your prediction

open on YouTube

Try it

Problem 20.6.2

What is the units digit of $19^{19} + 99^{99}$ ?

Problem 20.6.8(additional)

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

Problem 20.6.9(additional)

Find the units digit of $7^{109} - 3^{336}$

Contest cornerreal contest problems

Problem 20.6.1

AMC 8

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

Problem 20.6.12(additional)

AMC 10/12

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?

(A) 0 · (B) 4 · (C) 6 · (D) 7 · (E) 9

Problem 20.6.16(additional)

Omega Learn

In the Fibonacci sequence, how many of the first 100 terms in the sequence leave a remainder of less than 7 when divided by 8?

Checkpoint for section 20.5

Get 2 of 3 right to master this section. One try each, no hints.

20.6

Practice Problems

In this section you will be able to mix the product rule, cycles and combined mods on contest problems.

One more tough one, from the AIME! Pair up the squares, simplify, and only then reduce mod 1000. Every problem has three hints if you get stuck.

Want every problem from this chapter on one page? Open the problem set.

Contest cornerreal contest problems

Problem 20.6.15(additional)

AIME

Let $N = 100^2 + 99^2 - 98^2 - 97^2 + 96^2 + \cdots + 4^2 + 3^2 - 2^2 - 1^2$ , where the additions and subtractions alternate in pairs. Find the remainder when $N$ is divided by 1000.