Number Theory · Chapter 24

Modular Arithmetic

Work with remainders instead of huge numbers: wrap around a clock, spot digit cycles, and use Euler, Fermat, Wilson and the Chinese Remainder Theorem to tame enormous powers.

What's this chapter about?

24.0a Congruences and Cycles
24.0b Euler, Fermat, Wilson and the Binomial Theorem
24.0c CRT and Linear Congruences
24.1 Practice Problems

You'll need

24.0a0%

Congruences and Cycles

In this section you will be able to replace big numbers by their remainders, use negative remainders, and find the cycle of a power.

open on YouTube

Multiply $9 \times 99 \times 999 \times \cdots$ all the way to a number with 999 nines. The last three digits? Every factor after the second is $-1$ mod $1000$ .

Modular arithmetic only keeps the remainder. Think of a clock with $m$ spots: $17$ on a 6-hour clock is the same spot as $5$ .

Look: you can swap any number for its remainder before you add, multiply or take powers. The answer lands on the same spot. A negative name often helps: $999 \equiv -1 \pmod{1000}$ .

Exploreplay first, formulas later

Try this: With m = 1000, 99 × 999 lands on the same spot as 99 × (−1). Turn on Negative names: why is 999 ≡ −1?
Try this: Press Residue classes, set m = 5 and N = 30. Residues 1 and 4 can't both be in S. Which class would you take?
Try this: Press a to the b with m = 10 and a = 2. Step b from 1 to 8. How long is the cycle of 2^k mod 10?

Name it

Definition 24.0.1 · Congruence

n \equiv a \pmod{b}

means that the number $n$ leaves the same remainder as $a$ when divided by $b$ . Equivalently, $b$ divides $n - a$ . Read it as “ $n$ is congruent to $a$ mod $b$ ”.

Theorem 24.0.2 · Multiplying Congruences

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

ab \equiv xy \pmod{n}.

(The book prints the first congruence as “ $a = x \pmod n$ ”; it means $\equiv$ .)

Theorem 24.0.3 · Powers of Congruences

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

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

for every positive integer $m$ .

Concept 24.0.4 · Digit Cycles

To find the last digit(s) of a huge power $a^b$ , compute the first few values of $a^b$ and look for a pattern. The remainders must eventually repeat, so the pattern carries over to large $b$ .

Watch itpredict, then reveal

Example 24.1

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
By Theorem 24.0.2 you may replace every factor by its remainder mod $1000$ . What is $999$ mod $1000$ , written as a negative number?

Predict first:
Your prediction

open on YouTube

Example 24.2

AMC 12

Let $S$ be a subset of $\{1, 2, 3, \dots, 30\}$ with the property that no pair of distinct elements in $S$ has a sum divisible by $5$ . What is the largest possible size of $S$ ?

1
Whether a sum is divisible by $5$ depends only on the remainders. Sort $1, \dots, 30$ by remainder mod $5$ . How many numbers land in each class?

Predict first:
Your prediction

open on YouTube

Example 24.3

AMC 12

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

1
What is the units digit of $2008^2$ ?

Predict first:
Your prediction

open on YouTube

Try it

Problem 24.1.1

Omega Learn

Find the remainder when $36^9$ is divided by $5$ .

Problem 24.1.2

Omega Learn

Find the remainder when $34^9$ is divided by $5$ .

Contest cornerreal contest problems

Problem 24.1.18(additional)

AMC 10

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

Problem 24.1.12

AMC 10

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

Problem 24.1.21(additional)

AMC 10

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

Checkpoint for section 24.0a

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

24.0b0%

Euler, Fermat, Wilson and the Binomial Theorem

In this section you will be able to count with Euler's φ, shrink huge exponents with Euler and Fermat, find inverses, and use Wilson and the binomial theorem.

open on YouTube

What is $6^{83} + 8^{83}$ mod $49$ ? Powers of $6$ mod $49$ repeat, and the cycle length divides $\varphi(49) = 42$ . So $6^{83}$ is really $6^{-1}$ .

$\varphi(n)$ counts the numbers from $1$ to $n$ that share no factor with $n$ . Strike out the multiples of each prime factor and count what is left.

Look: when $\gcd(a, n) = 1$ , $a^{\varphi(n)} \equiv 1 \pmod n$ . So you can cut any exponent down mod $\varphi(n)$ . For a prime $p$ this is Fermat: $a^{p-1} \equiv 1$ .

Exploreplay first, formulas later

Try this: Strike the multiples of 2, then 3, for n = 36. Each strike keeps the fraction (1 − 1/p) of what was left. Why?
Try this: Set n = 49. There is only one prime to strike. Why is φ(49) = 49 − 7 = 42?
Try this: Set n = 13, a prime, and strike. How many survive? That is why Fermat's exponent is p − 1.

Name it

Theorem 24.0.5 · Euler's Totient Function

If $n$ has the prime factorization $p_1^{e_1} p_2^{e_2} \cdots p_k^{e_k}$ , then

\varphi(n) = n\left(1 - \frac{1}{p_1}\right)\left(1 - \frac{1}{p_2}\right)\cdots\left(1 - \frac{1}{p_k}\right),

where $\varphi(n)$ is the number of positive integers $\le n$ that are relatively prime to $n$ .

Steps: 1. Find the prime factorization of $n$ . 2. For each prime $p_i$ , form $1 - \frac{1}{p_i}$ and multiply them. 3. Multiply that product by $n$ .

Theorem 24.0.6 · Euler's Totient Theorem

For $n > 1$ ,

a^{\varphi(n)} \equiv 1 \pmod{n}

if and only if $\gcd(a, n) = 1$ .

base6

mod49

$6^{1}$ 6
$6^{2}$ 36
$6^{3}$ 20
$6^{4}$ 22
$6^{5}$ 34
$6^{6}$ 8
$6^{7}$ 48
$6^{8}$ 43
$6^{9}$ 13
$6^{10}$ 29
$6^{11}$ 27
$6^{12}$ 15
$6^{13}$ 41
$6^{14}$ 1

The remainders mod 49 repeat every 14 powers: 6, 36, 20, 22, 34, 8, 48, 43, 13, 29, 27, 15, ….

φ(49) = 42, and the cycle length 14 divides 42

cycle length 14

Corollary 24.0.7 · Fermat's Little Theorem

If $p$ is a prime and $p \nmid a$ , then

a^{p-1} \equiv 1 \pmod{p}.

(The book says “if and only if $p$ is a prime and $\gcd(a, n) = 1$ ”. The converse is false: $561 = 3 \cdot 11 \cdot 17$ is not prime, yet $a^{560} \equiv 1 \pmod{561}$ for every $a$ coprime to $561$ .)

Concept 24.0.8 · Modular Inverses

If $ab \equiv 1 \pmod{n}$ , then $a$ is the modular inverse of $b$ (mod $n$ ), and $b$ is the inverse of $a$ . We write

a^{-1} \equiv b \pmod{n}.

An inverse of $a$ exists exactly when $\gcd(a, n) = 1$ .

Theorem 24.0.9 · Wilson's Theorem

For a prime $p$ ,

(p-1)! \equiv p - 1 \equiv -1 \pmod{p}.

Theorem 24.0.10 · Binomial Theorem

For non-negative $n$ ,

(x+y)^n = \binom{n}{0}x^n y^0 + \binom{n}{1}x^{n-1}y + \binom{n}{2}x^{n-2}y^2 + \cdots + \binom{n}{n}x^0 y^n.

In modular arithmetic, write a big base as “small number + multiple of 10”: in $(1 + 10)^{n}$ every term from $10^3$ on vanishes mod $1000$ , so $(1 + 10)^n \equiv 1 + 10n + 100\binom{n}{2} \pmod{1000}$ .

Watch itpredict, then reveal

Example 24.4

AIME

Let $a_n = 6^n + 8^n$ . Determine the remainder upon dividing $a_{83}$ by $49$ .

base6

mod49

$6^{1}$ 6
$6^{2}$ 36
$6^{3}$ 20
$6^{4}$ 22
$6^{5}$ 34
$6^{6}$ 8
$6^{7}$ 48
$6^{8}$ 43
$6^{9}$ 13
$6^{10}$ 29
$6^{11}$ 27
$6^{12}$ 15
$6^{13}$ 41
$6^{14}$ 1

The remainders mod 49 repeat every 14 powers: 6, 36, 20, 22, 34, 8, 48, 43, 13, 29, 27, 15, ….

φ(49) = 42, and the cycle length 14 divides 42

cycle length 14

1
Euler's theorem needs $\varphi(49)$ . What is it?

Predict first:
Your prediction

open on YouTube

Example 24.5

AMC 10

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

1
Only the last three digits matter, so work mod $1000$ . What is $2011 \bmod 1000$ ?

Predict first:
Your prediction

open on YouTube

Try it

Problem 24.1.3

Omega Learn

Find the remainder when $7^{803}$ is divided by $400$ .

Contest cornerreal contest problems

Problem 24.1.4

AMC 10

An integer $N$ is selected at random in the range $1 \le N \le 2020$ . What is the probability that the remainder when $N^{16}$ is divided by $5$ is $1$ ?

Problem 24.1.11

AMC 10

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

Problem 24.1.26(additional)

AMC 10/12Challenge

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

Checkpoint for section 24.0b

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

24.0c0%

CRT and Linear Congruences

In this section you will be able to solve systems of congruences with the Chinese Remainder Theorem, by guess and check or by algebra.

open on YouTube

Find a number above $100$ that leaves remainder $5$ when divided by $9$ and remainder $4$ when divided by $17$ . Guessing works, but there is a faster way.

Each congruence picks out every $m$ -th number. When the moduli share no factor, the two patterns line up exactly once in every $m_1 m_2$ numbers. That is the Chinese Remainder Theorem.

Look: to solve it by algebra, write $n = 9k + 5$ and put that into the second congruence. You only need one inverse.

Exploreplay first, formulas later

remainder 15

mod 19

remainder 24

mod 217

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

153

154

155

156

157

158

159

160

161

162

163

164

165

166

167

168

169

170

171

172

173

174

175

176

177

178

179

180

181

182

183

184

185

186

187

188

189

190

191

192

193

194

195

196

197

198

199

140

Try this: Read the dots: one color marks ≡ 5 (mod 9), the other ≡ 4 (mod 17). Which number has both? How far is it from the next one?
Try this: Change the moduli to 4 and 6, with remainders 1 and 2. Why does nothing light up?
Try this: Add a third condition. How far apart are the matches now? Compare with the product of the moduli.

Name it

Theorem 24.0.11 · Chinese Remainder Theorem

If a positive number $x$ satisfies

x \equiv a_1 \pmod{n_1},\quad x \equiv a_2 \pmod{n_2},\quad \dots,\quad x \equiv a_k \pmod{n_k},

where the $n_i$ are pairwise relatively prime, then $x$ has a unique solution modulo $n_1 n_2 \cdots n_k$ .

Remark 24.0.12

Be careful! This may fail if some $n_i$ share a common factor: the congruences might contradict each other. For example, $x \equiv 1 \pmod 4$ says $x$ is odd, while $x \equiv 2 \pmod 6$ says $x$ is even.

Concept 24.0.13 · Solving Linear Congruences

To solve a pair of congruences you can either guess and check until a number satisfies both, or use the algebraic method:

Start with $n \equiv r_1 \pmod{m_1}$ and $n \equiv r_2 \pmod{m_2}$ , with $m_1$ and $m_2$ relatively prime.
Rewrite the first algebraically: $n = k m_1 + r_1$ .
Put it into the second: $k m_1 + r_1 \equiv r_2 \pmod{m_2}$ , so $k \equiv (r_2 - r_1)\cdot m_1^{-1} \pmod{m_2}$ .
Find $m_1^{-1} \pmod{m_2}$ by guess and check.
Now you know $k \equiv k_0 \pmod{m_2}$ ; write $k = m_2 t + k_0$ .
Substitute back into $n = k m_1 + r_1$ .
Read off the final congruence $n \equiv k_0 m_1 + r_1 \pmod{m_1 m_2}$ .

(The book's step 3 reads “ $m_1 \equiv (r_2 - r_1)\cdot k^{-1}$ ”, and step 5 uses undefined letters $b, d$ ; fixed here.)

Concept 24.0.14 · The Two-Congruence Formula

For relatively prime $m_1, m_2$ , the solution of $n \equiv r_1 \pmod{m_1}$ and $n \equiv r_2 \pmod{m_2}$ is

n \equiv r_1 + m_1 (r_2 - r_1)\cdot i \pmod{m_1 m_2}, \qquad \text{where } i \equiv m_1^{-1} \pmod{m_2}.

(The book leaves out the final modulus $m_1 m_2$ .)

Remark 24.0.15

To solve more than two congruences, solve them two at a time until only one congruence is left.

Watch itpredict, then reveal

Example 24.6

Omega Learn

Find the smallest positive integer greater than $100$ that leaves a remainder of $5$ when divided by $9$ and leaves a remainder of $4$ when divided by $17$ .

1
Write $n = 9k + 5$ . The second condition says $9k + 5 \equiv 4 \pmod{17}$ . So $9k \equiv ? \pmod{17}$ (use a remainder from $0$ to $16$ )

Predict first:
Your prediction

open on YouTube

Example 24.7

AIME

The positive integers $N$ and $N^2$ both end in the same sequence of four digits $abcd$ when written in base $10$ , where digit $a$ is not zero. Find the three-digit number $abc$ .

remainder 10

mod 116

9300

9301

9302

9303

9304

9305

9306

9307

9308

9309

9310

9311

9312

9313

9314

9315

9316

9317

9318

9319

9320

9321

9322

9323

9324

9325

9326

9327

9328

9329

9330

9331

9332

9333

9334

9335

9336

9337

9338

9339

9340

9341

9342

9343

9344

9345

9346

9347

9348

9349

9350

9351

9352

9353

9354

9355

9356

9357

9358

9359

9360

9361

9362

9363

9364

9365

9366

9367

9368

9369

9370

9371

9372

9373

9374

9375

9376

9377

9378

9379

9380

9381

9382

9383

9384

9385

9386

9387

9388

9389

9390

9391

9392

9393

9394

9395

9396

9397

9398

9399

1
Write the condition as a congruence. What must $N(N - 1)$ be divisible by?

Predict first:
Your prediction

open on YouTube

Try it

Problem 24.1.6

Omega Learn

Find the smallest positive number that leaves a remainder of $11$ when divided by $13$ and a remainder of $2$ when divided by $5$ .

Contest cornerreal contest problems

Problem 24.1.20(additional)

AMC 10

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

Problem 24.1.15

AMC 12

Let $S$ be the set of all integers $z > 1$ such that for all pairs of nonnegative integers $(x, y)$ with $x < y < z$ , the remainder when $2025x$ is divided by $z$ is less than the remainder when $2025y$ is divided by $z$ . What is the sum of the elements of $S$ ?

Checkpoint for section 24.0c

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

24.1

Practice Problems

In this section you will be able to mix every tool of the chapter on contest problems.

The rest of the practice set, from AMC 10 warm-ups to AIME 13s. First ask: which modulus makes the problem small?

Contest cornerreal contest problems

Problem 24.1.5

PUMaC

If $p$ , $q$ and $r$ are primes with $pqr = 7(p + q + r)$ , find $p + q + r$ .

Problem 24.1.7

AMC 10

This problem also appears in the book as 21.3.21.

What is the hundreds digit of $(20! - 15!)$ ?

Problem 24.1.8

AMC 10

This problem also appears in the book as 21.3.19.

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

Problem 24.1.9

AMC 10

Which of the following expressions is never a prime number when $p$ is a prime number?

Problem 24.1.10

AMC 12

Let $S(n)$ equal the sum of the digits of positive integer $n$ . For example, $S(1507) = 13$ . For a particular positive integer $n$ , $S(n) = 1274$ . Which of the following could be the value of $S(n+1)$ ?

Problem 24.1.13

AMC 12

This problem also appears in the book as 21.3.20.

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

Problem 24.1.14

AMC 10/12

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

Problem 24.1.16

AIME

Let $p$ be the least prime number for which there exists a positive integer $n$ such that $n^4 + 1$ is divisible by $p^2$ . Find the least positive integer $m$ such that $m^4 + 1$ is divisible by $p^2$ .

Problem 24.1.17

AMC 10/12Challenge

Let $x_0, x_1, x_2, \dots$ 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 \ge 1$ . What is the value of the sum

x_{2019} + 2x_{2020} + 4x_{2021} + 8x_{2022}?

Problem 24.1.19(additional)

AMC 10

What is the greatest power of $2$ that is a factor of $10^{1002} - 4^{501}$ ?

Problem 24.1.22(additional)

AIME

For positive integers $N$ and $k$ , define $N$ to be $k$ -nice if there exists a positive integer $a$ such that $a^k$ has exactly $N$ positive divisors. Find the number of positive integers less than $1000$ that are neither $7$ -nice nor $8$ -nice.

Problem 24.1.23(additional)

AIME

Let $S$ be the set of integers between $1$ and $2^{40}$ whose binary expansions have exactly two $1$ 's. If a number is chosen at random from $S$ , the probability that it is divisible by $9$ is $p/q$ , where $p$ and $q$ are relatively prime positive integers. Find $p + q$ .

Problem 24.1.24(additional)

AIME

It is known that, for all positive integers $k$ ,

1^2 + 2^2 + 3^2 + \cdots + k^2 = \frac{k(k+1)(2k+1)}{6}.

Find the smallest positive integer $k$ such that $1^2 + 2^2 + 3^2 + \cdots + k^2$ is a multiple of $200$ .

Problem 24.1.25(additional)

AIME

Find the sum of all positive integers $n$ such that when $1^3 + 2^3 + 3^3 + \cdots + n^3$ is divided by $n + 5$ , the remainder is $17$ .