Modular Arithmetic: Level 1

AMC 10 Foundational Practice Paper

Prepared for Competition Math Enthusiasts

Instructor’s Note: This paper serves as the foundational tier in our modular arith-
metic sequence. While designated as ”Level 1,” these problems are designed in the
spirit of the AMC 10. They transcend mere computation, requiring the student to
identify underlying structures, establish cyclic patterns, and apply fundamental the-
orems (such as Fermat’s Little Theorem and the rudiments of the Chinese Remainder
Theorem) in slightly obfuscated contexts. A thorough mastery of these 40 problems
is prerequisite for the more abstraction-heavy tiers that follow. Ensure every step of
your reasoning is rigorous.

The Problems

Problem 1. Let N be the integer obtained by computing the product of the first ten positive
prime numbers. Determine the remainder when N is divided by 12.

Problem 2. Consider the sequence defined by an = n2 +3n+5 for all positive integers n. Find the
smallest positive integer k such that both ak and ak+1 leave the same remainder when divided
by 7.

Problem 3. Suppose x and y are positive integers such that 3x + 4y ≡ 5 (mod 11). If x ≡ 6
(mod 11), find the unique integer r ∈ {0, 1, 2, . . . , 10} such that y ≡ r (mod 11).

Problem 4. Let S be the sum of the first 100 positive even integers. Determine the remainder
when S is divided by 101.

Problem 5. If the polynomial P (x) = x4 − ax3 + bx2 − cx + d evaluates to a multiple of 5 for

Problem 6. Find the smallest positive integer n such that the number represented as 123n (in
base n) is divisible by 7.

Problem 7. Two standard, six-sided dice are rolled, and the sum of the numbers on the top
faces is calculated. Let P be the product of all possible distinct sums. Find the remainder when
P is divided by 13.

Problem 8. Let A be a 3-digit positive integer. When A is divided by 9, the remainder is 4. When
the sum of the digits of A is divided by 5, the remainder is 2. What is the smallest possible value
of A?

Problem 9. Consider the set M = {1, 2, 3, . . . , 20}. How many distinct pairs (a, b) of elements
from M (where order matters, so (a, b) is distinct from (b, a)) satisfy the condition that a2 − b2 is
a multiple of 5?

1
Problem 10. A factory produces widgets in batches. If they pack the widgets in boxes of 12,
they have 7 left over. If they pack them in boxes of 8, they have 3 left over. If the total number of
widgets produced in a day is less than 100, what is the maximum number of widgets they could
have produced?

Problem 11. Determine the units digit of the integer 34 .

Problem 12. Find the remainder when the massive sum 15 + 25 + 35 + · · · + 995 + 1005 is divided
by 4.

Problem 13. Let N = 20232024 + 20242025 + 20252026 . Determine the remainder when N is divided
by 10.

Problem 14. Find the last two digits of the number 72026 .

Problem 15. Determine the remainder when 555 · 222 is divided by 7.

Problem 16. Let Fn denote the n-th Fermat number, defined as Fn = 22 +1. Find the remainder
n

when F5 is divided by 3.

Problem 17. What is the units digit of the sum of the first 100 terms of the geometric sequence
2, 4, 8, 16, . . . ?

Problem 18. Find the smallest integer n > 1 such that 3n ends in the digits 03.

Problem 19. Evaluate the remainder when (1! + 2! + 3! + · · · + 100!)2 is divided by 15.

Problem 20. The number A is formed by concatenating the first 20 positive integers: A =
123456789101112 . . . 1920. Find the remainder when A is divided by 9.

Problem 21. Find the sum of all positive integers x < 100 that satisfy the congruence 14x ≡ 6
(mod 22).

Problem 22. Using Fermat’s Little Theorem or otherwise, compute the remainder when 11103
is divided by 101 (note that 101 is prime).

Problem 23. Find the unique positive integer a < 17 such that the linear congruence ax ≡ 1
(mod 17) has a solution x that satisfies x2 ≡ 2 (mod 17).

Problem 24. Let p be a prime number strictly greater than 3. Prove, by considering congruences
modulo 24, that p2 − 1 is always a multiple of 24. You do not need to submit a proof, but use this
fact to find the remainder when 232 + 292 + 312 + 372 is divided by 24.

Problem 25. Find the smallest positive integer n such that 2n ≡ n (mod 5).

Problem 26. Determine the modular inverse of 25 modulo 72.

Problem 27. Find the remainder when 100100 is divided by 13.

Problem 28. Solve the system of linear congruences for the smallest positive integer x: 2x ≡ 1
(mod 5) and 3x ≡ 2 (mod 7).

Problem 29. If p = 19 and q = 23, find the remainder when pq−1 + q p−1 is divided by p · q.

2
Problem 30. Find the number of integers n in the set {1, 2, . . . , 100} such that n12 − 1 is divisible
by 13.

Problem 31. Evaluate ϕ(360), where ϕ denotes Euler’s Totient function, and use it to find the
number of positive integers less than 360 that are not relatively prime to 360.

Problem 32. Find the remainder when 3ϕ(50) is divided by 25.

Problem 33. A troop of monkeys has a number of bananas. If they divide the bananas equally
among 5 monkeys, 2 are left over. If they divide them among 7 monkeys, 3 are left over. If
they divide them among 11 monkeys, 4 are left over. What is the smallest possible number of
bananas the troop could have?

Problem 34. Find the smallest positive integer x satisfying the system:

x≡2 (mod 3)
x≡3 (mod 5)
x≡4 (mod 7)

Problem 35. Let S be the set of all integers n such that 1 ≤ n ≤ 1000 and gcd(n, 42) = 1. Find
the number of elements in S.

Problem 36. Determine the last three digits of 78003 .

Problem 37. Find the smallest positive integer k such that k ≡ 1 (mod 2), k ≡ 2 (mod 3), k ≡ 3
(mod 4), k ≡ 4 (mod 5), and k ≡ 5 (mod 6).

Problem 38. Calculate ϕ(10!) − 10! · (1 − 12 )(1 − 13 )(1 − 15 )(1 − 17 ). (Determine if the expression
equals 0 or something else).

Problem 39. Find the remainder when 52024 is divided by 18.

Problem 40. An integer N leaves a remainder of a when divided by 10 and a remainder of b