Senior number theory problems (ages 16 to 18)

Answer: D, 4 × 1013² = 4 104 676

1. Factorise: 2026 = 2 × 1013, with 1013 prime.
2. A whole number is a perfect cube exactly when every prime in its factorisation has an exponent that is a multiple of 3.
3. 2026k must therefore contain 2³ and 1013³ at least. 2026 already has 2¹ and 1013¹, so k must supply 2² and 1013².
4. Nothing else is needed, and any other prime in k would have to appear cubed, making k bigger. So k = 2² × 1013².
5. Then 2026k = 2³ × 1013³ = 2026³. ✓ k = 4 × 1013² = 4 104 676 (D).

Why this works: Perfect powers are recognised from prime factorisations: n is a perfect m-th power exactly when every exponent is a multiple of m.

Where it leads: Making a number a perfect power by multiplying is done prime by prime: raise each exponent to the next multiple of the power.

Answer: 29

1. We need 3²⁰²⁶ mod 100. Find a power of 3 that is ≡ 1 (mod 100).
2. 3⁵ = 243 ≡ 43. Square: 3¹⁰ ≡ 43² = 1849 ≡ 49.
3. Square again: 3²⁰ ≡ 49² = 2401 ≡ 1 (mod 100). So the last two digits repeat every 20 powers.
4. 2026 = 20 × 101 + 6, so 3²⁰²⁶ ≡ 3⁶ (mod 100).
5. 3⁶ = 729, so the last two digits are 29.

Why this works: Once a power is ≡ 1 mod 100 the last two digits cycle. Repeated squaring (3⁵, 3¹⁰, 3²⁰) finds the cycle quickly.

Where it leads: The cycle length 20 divides φ(100) = 40, as Euler’s theorem says it must.

Answer: 579

1. Whether 7 divides n² + n + 1 depends only on n mod 7.
2. Test n = 0, 1, 2, 3, 4, 5, 6: n² + n + 1 = 1, 3, 7, 13, 21, 31, 43. Only n ≡ 2 (7) and n ≡ 4 (21) are multiples of 7.
3. Numbers from 1 to 2026 of the form 7k + 2: need 7k + 2 ≤ 2026, so k = 0, 1, …, 289: 290 numbers.
4. Of the form 7k + 4: 7k + 4 ≤ 2026 gives k ≤ 288.9, so k = 0 to 288: 289 numbers.
5. Total: 290 + 289 = 579.

Why this works: Divisibility by 7 of a polynomial in n depends only on n mod 7, so a check of 7 cases settles every n; then it is a counting exercise.

Where it leads: n² + n + 1 divides n³ − 1, so the solutions are the n with n³ ≡ 1, n ≠ 1: cube roots of unity mod 7.

Answer: C, 130

1. 1000 = 2³ × 5³, so its divisors are 2^a5^b with a, b from 0 to 3.
2. A divisor is a perfect square when both exponents are even: a, b ∈ {0, 2}.
3. The square divisors are 1, 4, 25, 100.
4. Their sum is 1 + 4 + 25 + 100 = 130, which also equals (1 + 2²)(1 + 5²) = 5 × 26.
5. Answer: 130 (C).

Why this works: Sums over divisors factorise: the sum of 2^a5^b over the allowed a and b is (sum of allowed 2-powers) × (sum of allowed 5-powers).

Where it leads: The sum factorises: (1 + 4)(1 + 25) = 130, because the divisor-sum function is multiplicative.

Answer: 30

1. Factorise: x² − y² = (x − y)(x + y) = 2025. Put u = x − y and v = x + y, so uv = 2025.
2. Conversely x = (u + v)/2 and y = (v − u)/2, which are integers exactly when u and v have the same parity.
3. 2025 is odd, so any factor pair (u, v) has both factors odd: every factor pair gives a solution, and different pairs give different (x, y).
4. 2025 = 3⁴ × 5² has (4 + 1)(2 + 1) = 15 positive divisors, so 15 ordered pairs (u, v) with u, v > 0.
5. Negative pairs (−u, −v) also multiply to 2025: another 15.
6. Total: 30 integer solutions (for example u = 1, v = 2025 gives x = 1013, y = 1012).

Why this works: A difference of squares factorises, and the change of variables (u, v) ↔ (x, y) is one-to-one as long as u and v have the same parity.

Where it leads: 2025 = 3⁴ × 5² has 15 positive divisors, giving 15 ordered positive factor pairs, doubled for negative pairs.

Answer: 5

1. Split by the number of digits of 2026 in base b.
2. Two digits happen for 46 ≤ b ≤ 2026 (b² > 2026). A two-digit palindrome is ‘aa’ = a(b + 1) with 1 ≤ a < b.
3. So b + 1 divides 2026 = 2 × 1013: b + 1 = 1013 (a = 2, b = 1012) or b + 1 = 2026 (a = 1, b = 2025). (b + 1 = 2 is too small.)
4. Three digits happen when b² ≤ 2026 < b³, i.e. 13 ≤ b ≤ 45. A palindrome ‘a c a’ means 2026 = a(b² + 1) + cb.
5. Checking these bases: b = 13 gives digits 11, 12, 11 (11 × 170 + 12 × 13 = 2026); b = 14 gives 10, 4, 10 (10 × 197 + 56); b = 45 gives 1, 0, 1 (2025 + 1). No other base in 13–45 works.
6. For b ≤ 12 the number has four or more digits, and none of those representations is a palindrome.
7. Total: bases 13, 14, 45, 1012, 2025: 5.

Why this works: Base-b digits come from repeated division, and fixing the number of digits turns ‘palindrome’ into a small equation in b. Two-digit palindromes are always multiples of b + 1.

Where it leads: Every number n ≥ 3 is the palindrome 11 in base n − 1, so the interesting question is which numbers are palindromes in no smaller base (these are called strictly non-palindromic numbers)

Answer: D, 2026

1. 2026² = 2² × 1013², so n! needs at least two factors of the prime 1013 (the 2s are easy).
2. The prime 1013 appears in n! once for each multiple of 1013 that is at most n (1013² is far bigger than any n here).
3. Two factors need two multiples of 1013: 1013 and 2026. So n ≥ 2026.
4. 2026! contains 1013 and 2026 = 2 × 1013, and plenty of 2s, so it is divisible by 2026².
5. The smallest n is 2026 (D). (1013! up to 2025! contain 1013 only once.)

Why this works: Legendre’s idea: the power of a prime p in n! counts multiples of p, p², … up to n. For a large prime only the multiples of p itself matter.

Where it leads: The largest prime factor usually decides how big n must be for n! to be divisible by a given number.

Answer: 400

1. Squares modulo 5: 0² = 0, 1, 4, 9 ≡ 4, 16 ≡ 1. So n² ≡ 4 exactly when n ≡ 2 or 3 (mod 5).
2. In each block of 5 consecutive numbers, exactly 2 work.
3. 1000 = 200 blocks of 5, so the count is 200 × 2 = 400.

Why this works: Divisibility by 5 depends only on n mod 5, so checking one complete set of remainders settles every n.

Where it leads: −1 is a square mod p exactly when p = 2 or p ≡ 1 (mod 4). That fact underlies Fermat’s theorem on sums of two squares.

Answer: C, 4

1. By Fermat’s little theorem, 2¹⁰¹² ≡ 1 (mod 1013).
2. 2026 = 2 × 1012 + 2, so 2²⁰²⁶ = (2¹⁰¹²)² × 2² ≡ 1 × 4.
3. The remainder is 4 (C).

Why this works: Fermat’s little theorem gives a cycle length that divides p − 1, so the exponent only matters modulo 1012.

Where it leads: Fermat’s theorem is the basis of fast primality tests; numbers that pass them without being prime are pseudoprimes, like 341 = 11 × 31 for base 2.

Answer: 8

1. x² ≡ 1 (mod 105) exactly when it holds mod 3, mod 5 and mod 7.
2. Mod a prime p, x² − 1 = (x − 1)(x + 1) ≡ 0 forces x ≡ 1 or −1: 2 choices each.
3. By the Chinese remainder theorem each combination of choices gives exactly one x mod 105: 2 × 2 × 2 = 8.

Why this works: Splitting a modulus into coprime prime factors turns one hard congruence into several easy ones, and the Chinese remainder theorem glues the answers back.

Where it leads: So 1 has 8 square roots mod 105. Factoring a number N is equivalent to finding a non-trivial square root of 1 mod N, which is why RSA’s security rests on factoring.

Answer: 12

1. Repeated difference of squares: 3¹⁰²⁴ − 1 = (3 − 1)(3 + 1)(3² + 1)(3⁴ + 1)…(3⁵¹² + 1).
2. 3 − 1 = 2 contributes 2¹; 3 + 1 = 4 contributes 2².
3. Each of the 9 factors 3^2j + 1 (j = 1 to 9) is an odd square plus 1, which is 2 mod 4: exactly one factor of 2 each.
4. Total: 1 + 2 + 9 = 12.

Why this works: Factorising into pieces whose powers of 2 are easy to read off avoids computing the enormous number.

Where it leads: The lifting-the-exponent lemma gives this in one step: v₂(3ⁿ − 1) = v₂(3 − 1) + v₂(3 + 1) + v₂(n) − 1 for even n.

Answer: 3042

1. 2026 = 2 × 1013 with both factors prime, so its divisors are 1, 2, 1013 and 2026.
2. Their sum is (1 + 2)(1 + 1013) = 3 × 1014.
3. = 3042.

Why this works: The divisor-sum function is multiplicative: for coprime a and b, σ(ab) = σ(a)σ(b).

Where it leads: A number is perfect when σ(n) = 2n. Every even perfect number is 2^p−1(2^p − 1) with 2^p − 1 prime; nobody knows if an odd one exists.

Answer: 864

1. Mod 8: 2²⁰²⁶ ≡ 0.
2. Mod 125: φ(125) = 100, so 2²⁰²⁶ ≡ 2²⁶. 2⁷ = 128 ≡ 3, so 2²¹ ≡ 27 and 2²⁶ ≡ 27 × 32 = 864 ≡ 114.
3. Find x ≡ 114 (mod 125) with x ≡ 0 (mod 8): try 114, 239, 364, 489, 614, 739, 864. 864 = 8 × 108. ✓
4. The last three digits are 864.

Why this works: 1000 = 8 × 125 with coprime factors, so the Chinese remainder theorem lets you work with each part separately.

Where it leads: The powers of 2 modulo 1000 eventually cycle with period 100. Tricks like this let you find the last digits of towers like 2²²².

Answer: C, Only p = 3

1. If p ≠ 3, p is not a multiple of 3, so p² ≡ 1 (mod 3) and p² + 2 ≡ 0 (mod 3).
2. Then p² + 2 is a multiple of 3 greater than 3, so not prime. (p = 2 gives 6.)
3. p = 3 gives 11, which is prime. Answer: only p = 3 (C).

Why this works: Squares of non-multiples of 3 always leave remainder 1, so adding 2 lands on a multiple of 3.

Where it leads: The same trick shows that among p, p + 2, p + 4 at least one is a multiple of 3, so (3, 5, 7) is the only ‘prime triple’ of that shape.

Answer: 74

1. n! / n² = (n − 1)!/n, so we need n | (n − 1)!.
2. If n = p is prime, no factor of (p − 1)! is a multiple of p, so it fails. There are 25 primes up to 100.
3. If n = ab with 1 < a < b < n, both a and b appear in (n − 1)!, so it works. If n = p² with p > 2, then p and 2p are both below n, so it works. n = 4 fails (3! = 6). n = 1 works (1 divides 0! = 1).
4. So the count is 100 − 25 − 1 = 74 (all except the 25 primes and 4).

Why this works: Reducing to n | (n − 1)! and handling primes, products of distinct factors and squares of primes separately covers every case.

Where it leads: Wilson’s theorem sharpens this: (n − 1)! ≡ −1 (mod n) exactly when n is prime. It is a beautiful (but slow) primality test.