Modular Arithmetic: Level 2
AMC 10 Intermediate Practice Paper
Prepared for Competition Math Enthusiasts
Instructor’s Note: Welcome to Level 2. Having established a firm grounding in the
mechanics of congruences, cycles, and basic theorems in Level 1, you must now syn-
thesize these tools. The problems herein are crafted to mimic the intellectual de-
mands of the mid-to-late AMC 10. You will encounter intertwined conditions, larger
moduli requiring clever factorization, non-obvious applications of Euler’s Totient The-
orem, and scenarios where the Chinese Remainder Theorem is not merely a formula
to apply, but a perspective required to unravel the structure of the problem. Precision
in logic is paramount.
The Problems
Problem 1. Let S be the sum of the digits of the integer 9999 . Let T be the sum of the digits of
S, and let U be the sum of the digits of T . Given that 9999 = ak 10k + · · · + a1 10 + a0 , determine
the exact numerical value of U .
Problem 2. Consider the sequence of integers defined by x1 = 3 and xn+1 = 3xn for n ≥
1. Determine the smallest positive integer k such that the sequence (xn (mod k)) is strictly
periodic with period greater than 1, and the sequence never reaches a constant value modulo
k.
Problem 3. Find the smallest positive integer N such that N leaves a remainder of 2 when
divided by 3, a remainder of 3 when divided by 5, a remainder of 4 when divided by 7, and N is
a multiple of 11.
Problem 4. Let f (x) = x3 − 3x2 + 5x − 7. Determine the sum of all distinct primes p such that
there exists an integer n for which f (n) is a multiple of p, and p divides the discriminant of f (x)
or is closely related to the roots of f (x) in a specific way. More simply, find the sum of all primes
p such that the congruence x3 − 3x2 + 5x − 7 ≡ 0 (mod p) has exactly one root of multiplicity 3.
Problem 5. A positive integer n is called peculiar if ϕ(n) is a perfect square, where ϕ is Euler’s
totient function. Find the number of peculiar integers n such that 1 ≤ n ≤ 100.
Problem 6. Determine the remainder when the product of all positive integers less than 40
that are relatively prime to 40 is divided by 40.
Problem 7. Let Rn denote the repunit consisting of n ones: Rn = 11 . . . 1}. Find the smallest
| {z
n times
positive integer k > 1 such that Rk is divisible by k.
Problem 8. Find all pairs of positive integers (a, b) with a ≤ b such that gcd(a, b) = 1 and ab
divides a2 + b2 − 1.
1
Problem 9. Suppose p is a prime number such that p ≡ 1 (mod 4). By Wilson’s Theorem,
(p − 1)! ≡ −1 (mod p). It is known that there exists an integer x such that x2 ≡ −1 (mod p).
Express such an x in terms of factorials involving p.
Problem 10. Find the number of ordered triples (x, y, z) of integers such that 0 ≤ x, y, z < 100
and
x + y + z ≡ 0 (mod 100)
x2 + y 2 + z 2 ≡ 0 (mod 100)
Problem 11. Determine the last three digits of the enormous number 20272026
2025
.
Problem 12. Let M be the least common P30multiple of all integers from 1 to 30. What is the
M
highest power of 2 that divides the sum k=1 k ?
Problem 13. Find the sum of all two-digit prime numbers p for which there exists an integer a
such that a2 + a + 1 is a multiple of p.
Problem 14. Consider the polynomial P (x) = x10 +x9 +· · ·+x+1. Find the remainder when P (x5 )
is divided by P (x). Use this result to determine the remainder when the number 11111111111
(11 ones) divides 1050 + 1045 + · · · + 105 + 1.
Problem 15. A sequence of integers {an } is defined by a1 = 1, a2 = 1, and an = an−1 + an−2
for n ≥ 3 (the Fibonacci sequence). Prove that for any positive integer m, the sequence {an
(mod m)} is periodic. What is the maximum possible period modulo m = 10?
Problem 16. Find the number of positive integers n ≤ 1000 such that the number of divisors of
n is a power of 2, and n leaves a remainder of 3 when divided by 4.
Problem 17. Determine the smallest positive integer x that satisfies the system of non-linear
congruences:
x2 ≡ 1 (mod 8)
x3 ≡ 8 (mod 9)
4
x ≡1 (mod 5)
Problem 18. Let p and q be distinct prime numbers. Suppose that a is an integer such that
gcd(a, pq) = 1. Prove that a(p−1)(q−1) ≡ 1 (mod pq). Use this to find the remainder when 2120 is
divided by 143.
Problem 19. Find the sum of all positive integers n < 50 such that the congruence x2 ≡ −2
(mod n) has at least one solution.
Problem 20. Consider a circular arrangement of n lights, initially all off. You perform n passes.
On the k-th pass, you toggle the state (on to off, off to on) of every k-th light, starting from
the k-th light. For which values of n will exactly the lights at positions corresponding to perfect
squares be on after all n passes?
Problem 21. Evaluate the sum
P100
i=1 i · i! modulo 101.
Problem 22. Find the smallest integer N > 1 such that N divides 2N + 2.
2
Problem 23. Let S be the set of all integers x such that 1 ≤ x ≤ 2024 and x is not divisible by 2,
3, or 11. Find the sum of the elements in S modulo 2024.
Problem 24. Determine the number of solutions (x, y) to the congruence x2 + y 2 ≡ 0 (mod 25)
where 0 ≤ x, y < 25.
Problem 25. A sequence is defined by a0 = 0 and an = 2an−1 + 1 for n ≥ 1. Find the smallest
positive integer k such that ak is divisible by 101.
Problem 26. Find all prime numbers p such that p divides 2p + 1.
Problem 27. Let A be a set of 16 distinct integers. Show that there must exist two distinct,
non-empty subsets of A whose elements sum to the same value modulo 32768. Is this true for
modulo 65535?
Problem 28. Find the remainder when 20! is divided by 23. Use this to find the remainder when
19! is divided by 23.
Problem 29. Determine the number of positive integers a < 100 such that the linear congruence
ax ≡ 12 (mod 100) has exactly 4 incongruent solutions modulo 100.
Problem 30. Evaluate the remainder when the sum of the cubes of the first 50 positive integers
is divided by 51.
Problem 31. Find the smallest positive integer m such that 7m ≡ 1 (mod 1000).
Problem 32. Let p = 43. Find the number of quadratic residues modulo p. (An integer a is
a quadratic residue modulo p if there exists an integer x such that x2 ≡ a (mod p), and a 6≡ 0
(mod p)).
Problem 33. Determine the highest power of 5 that divides 1000!. Then, determine the number
of trailing zeros of 1000! when written in base 15.
Problem 34. Solve for x: 5x ≡ 4 (mod 11) where 1 ≤ x ≤ 10.
Problem 35. Find the remainder when 11 · 22 · 33 · · · 1010 is divided by 11.
Problem 36. Let N be the number of ways to place 5 indistinguishable balls into 3 distinguish-
able boxes. Find the remainder when N N is divided by 7.
Problem 37. A positive integer is called bizarre if it leaves a remainder of 1 when divided by
every prime p ≤ 13. Find the smallest bizarre number greater than 1.
Problem 38. Find the sum of all digits of the base-9 representation of the integer 8100 − 1.
Problem 39. Determine the number of integers n ∈ {1, 2, . . . , 200} such that n2 + 3n + 2 is a
multiple of 6.
Problem 40. Let p be an odd prime. Prove that the sum of the squares of the first p − 1 positive
integers is a multiple of p if and only if p > 3.