OmegaLearn.org Chapter 25.
Modular Arithmetic
Video Lectures
Modular Arithmetic Euler’s & Binomial Theorems Chinese Remainder Theorem & Line
Definition 25.0.1.
n ≡ a (mod b)
means the number ’n’ leaves the same remainder as ’a’ when divided by b
Theorem 25.0.2
If a = x (mod n) and b ≡ y (mod n), then
ab ≡ xy (mod n)
Theorem 25.0.3
If a ≡ x (mod n), then
am ≡ x m (mod n)
Example 25.1 (AIME)
Find the remainder when 9 × 99 × 999 × · · · × 99 · · · 9} is divided by 1000.
| {z
999 9’s
Video Solution
Example 25.2 (AMC 12)
Let S be a subset of {1, 2, 3, . . . , 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?
Video Solution
Concept 25.0.4 (Digit Cycles)
To calculate large digit(s) of a number ab , a strategy that may work is to just look for a
pattern by computing the first few values of ab and then seeing that the pattern will
repeat for large values of b.
271
OmegaLearn.org Chapter 25. Modular Arithmetic
Example 25.3 (AMC 12)
Let k = 20082 + 22008 . What is the units digit of k 2 + 2k ?
Video Solution
Theorem 25.0.5 (Euler’s Totient Function)
If number n has the prime factorization
pe11 · pe22 · pe33 . . . penn
then
1 1 1
! ! !
ϕ(n) = n · 1 − 1− ... 1 −
p1 p2 pn
where ϕ(n) denotes the number of positive integers less than or equal to n that are
relatively prime to n.
Steps to find totient of a number
1. Find prime factorization
2. For all primes, calculate and multiply
1
1−
pi
3. Multiply this product to the number n to get the totient
Theorem 25.0.6 (Euler’s Totient Theorem)
aϕ(n) ≡ 1 (mod n)
if and only if
gcd(a, n) = 1
272
OmegaLearn.org Chapter 25. Modular Arithmetic
Corollary 25.0.7 (Fermat’s Little Theorem)
ap−1 ≡ 1 (mod p)
if an only if p is a prime and
gcd(a, n) = 1
Concept 25.0.8 (Modular Inverses)
If a is denoted as the modular inverse of b (mod n), then
ab ≡ 1 (mod n)
We also write that
a−1 ≡ b (mod n)
since a and b are inverses (mod n).
Theorem 25.0.9 (Wilson’s Theorem)
(p − 1)! ≡ p − 1 ≡ −1 (mod p)
Example 25.4 (AIME)
Let an = 6n + 8n . Determine the remainder upon dividing a83 by 49.
Video Solution
Theorem 25.0.10 (Binomial Theorem)
For non-negative n,
! ! ! !
n n 0 n n−1 n n−2 2 n 0 n
(x + y) =
n
x y + x y+ x y + ··· + xy
0 1 2 n
273
OmegaLearn.org Chapter 25. Modular Arithmetic
Example 25.5 (AMC 10)
What is the hundreds digit of 20112011 ?
Video Solution
Theorem 25.0.11 (Chinese Remainder Theorem)
If a positive number x satisfies
x ≡ a1 (mod n1 )
x ≡ a2 (mod n2 )
..
.
x ≡ ak (mod nk )
where all ni are relatively prime, then x has a unique solution (mod n1 · n2 · n3 . . . nk )
Remark 25.0.12
Be careful! This may not necessarily be true if any ni share common factors as then
congruences might contradict each other.
Concept 25.0.13 (Solving Linear Congruences)
To solve a linear congruence with 2 congruences you can either
• Guess and Check until you reach a value that works and satisfies both mods
• Algebraic Method
1. Find 2 congruences
n ≡ r1 (mod m1 )
n ≡ r2 (mod m2 )
such that m1 and m2 are relatively prime
2. Rewrite them algebraically
n = k(m1 ) + r1
274
OmegaLearn.org Chapter 25. Modular Arithmetic
n = j(m2 ) + r2
3. Set them equal mod the smaller of m1 and m2 (in this case, say m1 < m2 )
k(m1 ) + r1 ≡ r2 (mod m2 ) =⇒ m1 ≡ (r2 − r1 ) · k −1 (mod m2 )
4. Guess and check to find the value of
k −1 (mod m2 )
5. Using the value of what b is (mod d), rewrite it algebraically.
6. Substitute it back into the expression
n = k(m1 ) + r1
7. Convert it back to mods to get the final congruence
Concept 25.0.14
The solution to
n ≡ r1 (mod m1 )
n ≡ r2 (mod m2 )
is
n ≡ r1 + m1 (r2 − r1 ) · i
where i ≡ m−1
1 (mod m2 )
Remark 25.0.15
To solve a general congruence of more than 2 congruences, just solve them 2 at a time
until you are left with just 1 congruence.
Example 25.6
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.
Video Solution
275
OmegaLearn.org Chapter 25. Modular Arithmetic
Example 25.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.
Video Solution
25.1 Practice Problems
Problem 25.1.1
Find the remainder 369 when it’s divided by 5.
Video Solution
Problem 25.1.2
Find the remainder 349 when it’s divided by 5.
Video Solution
Problem 25.1.3
Find the remainder when 7803 is divided by 400.
Video Solution
Problem 25.1.4 (AMC 10)
An integer N is selected at random in the range 1 ≤ N ≤ 2020 . What is the probability
that the remainder when N 16 is divided by 5 is 1?
276
OmegaLearn.org Chapter 25. Modular Arithmetic
Video Solution
Problem 25.1.5 (PUMAC)
If p, q and r are primes with pqr = 7(p + q + r), find p + q + r
Video Solution
Problem 25.1.6
Find the smallest positive number that leaves a remainder of 11 when divided by
13 and a remainder of 2 when divided by 5.
Problem 25.1.7 (AMC 10)
What is the hundreds digit of (20! − 15!)?
Video Solution
Problem 25.1.8 (AMC 10)
What is the tens digit of 20152016 − 2017?
Video Solution
Problem 25.1.9 (AMC 10)
Which of the following expressions is never a prime number when p is a prime number?
(A) p2 + 16 (B) p2 + 24 (C) p2 + 26 (D) p2 + 46 (E) p2 + 96
Video Solution
277
OmegaLearn.org Chapter 25. Modular Arithmetic
Problem 25.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)?
Video Solution
Problem 25.1.11 (AMC 10)
Let a1 , a2 , . . . , a2018 be a strictly increasing sequence of positive integers such that
a1 + a2 + · · · + a2018 = 20182018 .
What is the remainder when a31 + a32 + · · · + a32018 is divided by 6?
Video Solution
Problem 25.1.12 (AMC 10)
How many of the first 2018 numbers in the sequence 101, 1001, 10001, 100001, . . . are
divisible by 101?
Problem 25.1.13 (AMC 10)
Let a1 , a2 , . . . , a2018 be a strictly increasing sequence of positive integers such that
a1 + a2 + · · · + a2018 = 20182018 .
What is the remainder when a31 + a32 + · · · + a32018 is divided by 6?
Problem 25.1.14 (AMC 12)
Let N = 123456789101112 . . . 4344 be the 79-digit number that is formed by writ-
ing the integers from 1 to 44 in order, one after the other. What is the remainder when
N is divided by 45?
278
OmegaLearn.org Chapter 25. Modular Arithmetic
Video Solution
Problem 25.1.15 (AMC 10/12)
One of the following numbers is not divisible by any prime number less than 10. Which
is it? (A) 2606 − 1 (B) 2606 + 1 (C) 2607 − 1 (D) 2607 + 1 (E) 2607 + 3607
Video Solution
Problem 25.1.16 (AMC 10/12)
Let x0 , x1 , x2 , · · · be a sequence of numbers, where each xk is either 0 or 1. For
each positive integer n, define
n−1
Sn = xk 2k
X
k=0
Suppose 7Sn ≡ 1 (mod 2 ) for all n ≥ 1. What is the value of the sum
n
x2019 + 2x2020 + 4x2021 + 8x2022 ?
(A) 6 (B) 7 (C) 12 (D) 14 (E) 15
Video Solution
Additional Problems
Problem 25.1.17 (AMC 10)
What is the remainder when 30 + 31 + 32 + · · · + 32009 is divided by 8?
Problem 25.1.18 (AMC 10)
What is the greatest power of 2 that is a factor of 101002 − 4501 ?
279
OmegaLearn.org Chapter 25. Modular Arithmetic
(A) 21002 (B) 21003 (C) 21004 (D) 21005 (E) 21006
Problem 25.1.19 (AMC 10)
Let n be a 5-digit number, and let q and r be the quotient and the remainder, re-
spectively, when n is divided by 100. For how many values of n is q + r divisible by
11?
Problem 25.1.20 (AMC 10)
How many distinct four-digit numbers are divisible by 3 and have 23 as their last
two digits?
Problem 25.1.21 (AIME)
For positive integers N and k, define N to be k-nice if there exists a positive inte-
ger a such that ak has exactly N positive divisors. Find the number of positive integers
less than 1000 that are neither 7-nice nor 8-nice.
Problem 25.1.22 (AIME)
Let S be the set of integers between 1 and 240 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 25.1.23 (AIME)
It is known that, for all positive integers k,
12 + 22 + 32 + . . . + k 2 = k(k+1)(2k+1)
6
. Find the smallest positive integer k such that
1 + 2 + 3 + . . . + k is a multiple of 200.
2 2 2 2
Problem 25.1.24 (AIME)
Find the sum of all positive integers n such that when 13 + 23 + 33 + · · · + n3 is
280
OmegaLearn.org Chapter 25. Modular Arithmetic
divided by n + 5, the remainder is 17.
Problem 25.1.25 (AMC 10/12)
The number obtained from the last two nonzero digits of 90! is equal to n. What
is n?
Answers
25.1 109
25.2 13
25.3 6
25.4 035
25.5 6
25.6 140
25.7 937
25.1.1 1
25.1.2 −1
25.1.3 343
4
25.1.4 5
25.1.5 15
25.1.6 37
25.1.7 0
281
OmegaLearn.org Chapter 25. Modular Arithmetic
25.1.8 0
25.1.9 extbf (C)p2 + 26
25.1.10 1239
25.1.11 4
25.1.12 505
25.1.13 4
25.1.14 9
25.1.15 2607 − 1
25.1.16 6
25.1.17 4
25.1.18 21005
25.1.19 8181
25.1.20 30
25.1.21 749
25.1.22 913
25.1.23 112
25.1.24 239
25.1.25 12
282
