Intermediate number theory problems (ages 13 to 16)

Answer: 40

1. The last two digits of n² depend only on the last two digits of n, so work with n = 10a + b, where b is the units digit and a the tens digit.
2. n² ends in 1, so b² ends in 1: b = 1 or b = 9.
3. b = 1: n² = 100a² + 20a + 1. Its tens digit is the units digit of 2a, which must be 2, so a ends in 1 or 6: n ends in 11 or 61.
4. b = 9: n² = 100a² + 180a + 81. Its tens digit is the units digit of 18a + 8, i.e. of 8a + 8, which must be 2, so 8a ends in 4: a ends in 3 or 8: n ends in 39 or 89.
5. Check: 11² = 121, 39² = 1521, 61² = 3721, 89² = 7921. ✓
6. So 4 numbers in every block of 100, and 1 to 1000 is 10 blocks: 4 × 10 = 40.

Why this works: Working modulo 100 means you only ever look at the last two digits. Expanding (10a + b)² shows exactly which digit of n controls which digit of n².

Where it leads: Solving n² ≡ c modulo powers of 10 digit by digit is Hensel lifting, a key tool in number theory.

Answer: D, 37

1. N has twelve 1s. Split it as 111111 followed by 111111: N = 111111 × 1000000 + 111111 = 111111 × 1000001.
2. Split 111111 the same way: 111111 = 111 × 1000 + 111 = 111 × 1001.
3. 111 = 3 × 37 and 1001 = 7 × 11 × 13.
4. 1000001 = 101 × 9901, and neither 101 nor 9901 has a prime factor below 100 (101 is prime; 9901 is prime).
5. So the prime factors of N below 100 are 3, 7, 11, 13 and 37. In particular 31 and 41 do not divide N.
6. The largest is 37 (D).

Why this works: Numbers made of repeated digits split along their pattern: a block of 1s of length ab is (block of length a) × (1 000…01 …). 1001 = 7 × 11 × 13 is a factorisation worth knowing.

Where it leads: Repunits (numbers made of 1s) factor according to the divisors of their length; R_n can only be prime when n is prime.

Answer: 8

1. Rearrange ab = 2(a + b) + 20 as ab − 2a − 2b = 20.
2. Add 4 to both sides so the left factorises: ab − 2a − 2b + 4 = 24, i.e. (a − 2)(b − 2) = 24.
3. a and b are positive, so a − 2 ≥ −1 and b − 2 ≥ −1. Both brackets negative would need (−1)(−24), impossible, and one negative makes the product negative. So both brackets are positive.
4. Positive factor pairs of 24: 1 × 24, 2 × 12, 3 × 8, 4 × 6, and each in either order.
5. That gives (a, b) = (3, 26), (26, 3), (4, 14), (14, 4), (5, 10), (10, 5), (6, 8), (8, 6).
6. Check one: 6 × 8 = 48 and 2(6 + 8) + 20 = 48. ✓ There are 8 ordered pairs.

Why this works: Adding the right constant makes xy + px + qy factorise as (x + q)(y + p) − pq. Then a Diophantine equation becomes ‘list the factor pairs’.

Where it leads: Adding a constant to complete a product (Simon’s favourite factoring trick) turns many equations into divisor counts.

Answer: E, 6

1. Work modulo 7 (remainders on dividing by 7).
2. Powers of 2: 2, 4, 8 ≡ 1. So 2³ ≡ 1 and powers of 2 cycle with length 3.
3. 100 = 3 × 33 + 1, so 2¹⁰⁰ = (2³)³³ × 2 ≡ 1 × 2 = 2.
4. Powers of 3: 3, 2, 6, 4, 5, 1, so 3⁶ ≡ 1 and the cycle has length 6.
5. 100 = 6 × 16 + 4, so 3¹⁰⁰ ≡ 3⁴ = 81 = 77 + 4 ≡ 4.
6. Sum: 2 + 4 = 6, so the remainder is 6 (E).

Why this works: Once some power of a number leaves remainder 1, higher powers repeat in a cycle, so a huge exponent only matters through its remainder on dividing by the cycle length.

Where it leads: Fermat’s little theorem guarantees a⁶ ≡ 1 (mod 7) for every a not divisible by 7; the actual cycle may be shorter, like 3 for 2.

Answer: D, 2025

1. If n = p^a q^b … (prime factorisation), n has (a + 1)(b + 1)… divisors.
2. 15 = 15 or 15 = 3 × 5, so n = p¹⁴ or n = p⁴ q² for different primes p, q.
3. n is a multiple of 15, so both 3 and 5 divide n. That rules out p¹⁴ (one prime only) and forces {p, q} = {3, 5}.
4. The two options are 3⁴ × 5² = 81 × 25 = 2025 and 3² × 5⁴ = 9 × 625 = 5625.
5. The smaller is 2025 (D). (225 = 3²5² is a trap: it has only 3 × 3 = 9 divisors.)

Why this works: The divisor-count formula turns ‘exactly k divisors’ into ‘write k as a product’. To make n small, give the largest powers to the smallest primes.

Where it leads: To make a number with a given number of divisors as small as possible, give the biggest exponents to the smallest primes.

Answer: 10

1. Each zero at the end needs one factor 10 = 2 × 5, so count the 2s and the 5s.
2. 1 × 3 × 5 × … × 99 is a product of odd numbers, so it has no factor 2. The only 2s come from 2¹⁰: ten of them.
3. Factors of 5 in the odd product: the odd multiples of 5 up to 99 are 5, 15, 25, …, 95, which is 10 numbers.
4. 25 and 75 each contain 5 twice, adding 2 more: twelve 5s in total.
5. Pairs 2 × 5: min(10, 12) = 10, so there are 10 zeros.

Why this works: Trailing zeros count pairs 2×5. Usually 2s are plentiful and 5s are scarce; here the odd product has no 2s, so the 2s run out first.

Where it leads: Trailing zeros count the smaller of the powers of 2 and 5; here, unusually, the 2s are scarce.

Answer: 11

1. Write the number as 100a + 10b + c with a from 1 to 9 and b, c from 0 to 9.
2. The condition is 100a + 10b + c = 19(a + b + c) = 19a + 19b + 19c.
3. Rearrange: 81a = 9b + 18c, and divide by 9: 9a = b + 2c.
4. b + 2c is at most 9 + 18 = 27, so a is 1, 2 or 3.
5. a = 1: b + 2c = 9, with c = 0 to 4 (b = 9, 7, 5, 3, 1): 5 numbers (e.g. 190 = 19 × 10).
6. a = 2: b + 2c = 18, with c = 5 to 9 (b = 8, 6, 4, 2, 0): 5 numbers.
7. a = 3: b + 2c = 27 needs b = c = 9: 1 number, 399 = 19 × 21.
8. Total: 5 + 5 + 1 = 11.

Why this works: Digit problems collapse to small linear equations once the number is written in place-value form; bounding the digits keeps the case list short.

Where it leads: Digit equations become linear equations in a, b, c with small ranges, so a short search finishes them.

Answer: 4

1. Factors pair up as d and n/d, so a number has an odd number of factors only if it is a perfect square.
2. If n = m² has exactly 3 factors they are 1, m and m², so m has no factors other than 1 and itself: m is prime.
3. Squares of primes up to 100: 4, 9, 25, 49.
4. So 4 numbers.

Why this works: Pairing factors explains odd counts, and then the factor list 1, m, m² forces m to be prime.

Where it leads: The number of factors of p^aq^b… is (a + 1)(b + 1)…; exactly 3 factors needs (a + 1)(b + 1)… = 3, i.e. p².

Answer: B, 3

1. 3³ = 27 leaves remainder 1 on division by 13.
2. So 3⁹⁹ = (3³)³³ leaves remainder 1³³ = 1.
3. 3¹⁰⁰ = 3⁹⁹ × 3 leaves remainder 1 × 3 = 3 (B).

Why this works: Once a power leaves remainder 1, the remainders repeat in a cycle, so huge powers reduce to small ones.

Where it leads: Fermat’s little theorem guarantees 3¹² leaves remainder 1 on division by 13; the actual cycle length (here 3) always divides 12.

Answer: 72

1. Write n = 2^a3^b (extra primes would only make n larger).
2. 2n = 2^a+13^b is a square: a + 1 is even and b is even.
3. 3n = 2^a3^b+1 is a cube: a is a multiple of 3 and b + 1 is a multiple of 3.
4. Smallest a: odd and a multiple of 3, so a = 3. Smallest b: even with b + 1 a multiple of 3, so b = 2.
5. n = 2³ × 3² = 72. Check: 2n = 144 = 12², 3n = 216 = 6³. ✓

Why this works: Being a square or a cube is a condition on each prime’s exponent separately, so the problem splits into two small puzzles about remainders.

Where it leads: Combining conditions on exponents like this is the Chinese remainder theorem in action: a must be 3 mod 6.

Answer: 48

1. Multiples of 3 up to 100: ⌊100/3⌋ = 33, each giving one factor 3.
2. Multiples of 9: 11, each giving one extra 3.
3. Multiples of 27: 3 (27, 54, 81), one more each. Multiples of 81: 1, one more.
4. k = 33 + 11 + 3 + 1 = 48.

Why this works: Counting in layers (multiples of 3, then 9, then 27, …) counts each factor 3 exactly once.

Where it leads: This is Legendre’s formula. A neat consequence: the power of p in n! equals (n − digit sum of n in base p)/(p − 1). Check: 100 in base 3 is 10201, digit sum 4, (100 − 4)/2 = 48.

Answer: C, 15

1. 2²⁰ − 1 = 2⁸(2¹² − 1) + (2⁸ − 1), so HCF(2²⁰ − 1, 2¹² − 1) = HCF(2¹² − 1, 2⁸ − 1).
2. In the same way, HCF(2¹² − 1, 2⁸ − 1) = HCF(2⁸ − 1, 2⁴ − 1), and 2⁴ − 1 divides 2⁸ − 1.
3. The exponents follow Euclid’s algorithm on 20 and 12, ending at HCF(20, 12) = 4.
4. So the answer is 2⁴ − 1 = 15 (C).

Why this works: Subtracting multiples of 2^m − 1 from 2ⁿ − 1 mirrors subtracting m from n, so Euclid’s algorithm on the exponents carries over.

Where it leads: In general HCF(2^a − 1, 2^b − 1) = 2^{HCF(a, b)} − 1. So 2ⁿ − 1 can only be prime when n is prime (Mersenne primes).

Answer: 6

1. We need 100 − 5y to be a positive multiple of 3.
2. Remainders on division by 3: 100 → 1 and 5y → 2y, so 2y must leave remainder 1, i.e. y leaves remainder 2: y = 2, 5, 8, 11, 14, 17, …
3. x > 0 needs 5y < 100, so y ≤ 19. That allows y = 2, 5, 8, 11, 14, 17.
4. Each gives a positive x (30, 25, 20, 15, 10, 5), so there are 6 pairs.

Why this works: One solution of a linear equation in whole numbers leads to all of them: here y steps by 3 while x steps by 5.

Where it leads: ax + by = c has whole-number solutions exactly when HCF(a, b) divides c. The steps between solutions are b/h and a/h, where h = HCF(a, b).

Answer: 61

1. (1 + 10)²⁰²⁶ = 1 + 2026 × 10 + (terms containing 10² or higher powers).
2. Terms with 10² or more are multiples of 100, so they do not affect the last two digits.
3. 1 + 20260 = 20261, which ends in 61.
4. The last two digits are 61.

Why this works: The binomial expansion of (1 + 10)ⁿ shows that, modulo 100, only the first two terms survive.

Where it leads: So 11ⁿ always ends in the digits of 10n + 1 (mod 100). The same idea gives (1 + p)ⁿ ≡ 1 + np (mod p²), a key step in number theory.

Answer: 6

1. n² + 20 = (n + 2)(n − 2) + 24.
2. So n + 2 divides n² + 20 exactly when n + 2 divides 24.
3. With n ≥ 1, n + 2 ≥ 3. Factors of 24 from 3 upwards: 3, 4, 6, 8, 12, 24.
4. These give n = 1, 2, 4, 6, 10, 22: 6 values.

Why this works: Polynomial division turns ‘n + 2 divides a big expression’ into ‘n + 2 divides a fixed number’, leaving finitely many cases.

Where it leads: The remainder 24 is the value of n² + 20 at n = −2: the remainder theorem. It works for any polynomial divided by n − a.

Answer: D, 270

1. Powers of 2 in 10!: 5 + 2 + 1 = 8. Powers of 3: 3 + 1 = 4. Powers of 5: 2. Powers of 7: 1.
2. So 10! = 2⁸ × 3⁴ × 5² × 7.
3. A factor chooses each exponent independently: 9 × 5 × 3 × 2 = 270 (D).

Why this works: Counting factors only needs the exponents of the prime factorisation: add one to each and multiply.

Where it leads: Numbers with lots of factors for their size are called highly composite; Ramanujan studied them. 720720 has 240 factors.

Answer: 53

1. Numbers leaving remainder 4 on division by 7: 4, 11, 18, 25, 32, 39, 46, 53, …
2. Of these, remainder 3 on division by 5: 18 and then every 35 more: 18, 53, 88, …
3. Remainder 2 on division by 3: 18 leaves 0; 53 = 51 + 2 leaves 2. ✓
4. The answer is 53.

Why this works: Satisfying one condition at a time, and noting that solutions repeat every product of the divisors so far, keeps the search short.

Where it leads: The Chinese remainder theorem says there is exactly one solution below 3 × 5 × 7 = 105 because 3, 5 and 7 have no common factors.

Answer: 400

1. A number shares a factor with 1000 = 2³5³ exactly when it is divisible by 2 or by 5.
2. Divisible by 2: 500. By 5: 200. By both (by 10): 100. So by 2 or 5: 500 + 200 − 100 = 600.
3. The rest: 1000 − 600 = 400.

Why this works: Inclusion–exclusion over the prime factors of 1000 counts the numbers that share a factor, and the complement gives the answer.

Where it leads: This count is Euler’s totient φ(1000) = 1000 × (1 − 1/2)(1 − 1/5). It is the key number in RSA encryption.

Answer: A, 1

1. Divisibility by 11: the alternating digit sum 4 − d + 7 − d + 2 = 13 − 2d must be a multiple of 11.
2. For a digit d (0 to 9), 13 − 2d ranges from −5 to 13, so it must be 0 or 11.
3. 13 − 2d = 11 gives d = 1; 13 − 2d = 0 has no whole-number solution.
4. So d = 1 (A): 41712 = 11 × 3792. ✓

Why this works: 10 leaves remainder −1 on division by 11, so the digits contribute with alternating signs.

Where it leads: Similar tests exist for 7 and 13 using 1001 = 7 × 11 × 13: split the number into blocks of three digits and alternate signs.

Answer: 2

1. Write a = 12x and b = 12y, where x and y share no common factor (otherwise the HCF would be bigger).
2. ab = 144xy = 5184, so xy = 36.
3. Split 36 = 2² × 3² into two coprime parts: each prime power must go entirely to one side: {1, 36} and {4, 9}.
4. So the pairs are {12, 432} and {48, 108}: 2 pairs.

Why this works: Dividing out the HCF leaves two coprime numbers, and coprime numbers cannot share any prime, so each prime power goes to one side.

Where it leads: A number with k different prime factors splits into 2^k−1 unordered coprime pairs. Coprime splitting is key in problems about squares and Pythagorean triples.

Answer: 38

1. A square ends in 4 only if the number ends in 2 or 8.
2. Squares ending in 44: checking endings 02, 08, 12, …, the numbers ending in 12, 38, 62, 88 work (e.g. 12² = 144, 38² = 1444).
3. Try the smallest candidates: 12² = 144 (ends 144, not 444); 38² = 1444 (ends 444). ✓
4. The answer is 38.

Why this works: Building the ending one digit at a time (last digit, then last two) cuts a big search down to a handful of candidates.

Where it leads: No square ends in 4444: squares ending in 44 have the form 100k + 44 with restrictions mod 16. Working modulo powers of 10 one digit at a time is called Hensel lifting.

Answer: 18

1. A factor 2^a3^b5^c is a square exactly when a, b and c are all even.
2. a ∈ {0, 2, 4}: 3 choices. b ∈ {0, 2, 4} (b ≤ 5): 3 choices. c ∈ {0, 2}: 2 choices.
3. Total: 3 × 3 × 2 = 18.

Why this works: Squares are recognised prime by prime, so the choices for each exponent multiply.

Where it leads: The number of square factors of n equals the number of factors of the largest square dividing n’s ‘square root part’. Try counting cube factors the same way.

Answer: D, 74

1. a² − b² = (a − b)(a + b), and the two brackets differ by 2b, so they are both odd or both even.
2. Both odd: the product is odd. Both even: the product is a multiple of 4. So numbers leaving remainder 2 on division by 4 are impossible.
3. Every other number works: odd n = 2k + 1 = (k + 1)² − k²; n = 4k = (k + 1)² − (k − 1)².
4. From 1 to 99 there are 25 numbers of the form 4k + 2 (2, 6, …, 98), so 99 − 25 = 74 (D).

Why this works: Factorising a difference of squares and looking at parity both rules out a whole class and shows how to build every other number.

Where it leads: Sums of two squares are subtler: n is a sum of two squares exactly when every prime of the form 4k + 3 appears to an even power (Fermat and Euler).

Answer: 8

1. 1/7 = 0.142857 repeating, with period 6.
2. 2026 = 6 × 337 + 4, so the 2026th digit is the 4th digit of the block.
3. The block is 1, 4, 2, 8, 5, 7, so the 4th digit is 8.

Why this works: A repeating decimal is periodic, so only the remainder on division by the period matters.

Where it leads: 1/p has period dividing p − 1 for primes p other than 2 and 5. The period is p − 1 exactly when 10 is a ‘primitive root’ mod p (7, 17, 19, 23, …).

Answer: 6

1. 2026 = 2 × 729 + 568. 568 = 2 × 243 + 82. 82 = 1 × 81 + 1. 1 = 0 × 27 + 0 × 9 + 0 × 3 + 1.
2. So 2026 in base 3 is 2210001.
3. Digit sum: 2 + 2 + 1 + 0 + 0 + 0 + 1 = 6.

Why this works: Converting to base 3 means taking out the largest powers of 3 greedily, just as in base 10.

Where it leads: The base-3 digit sum also tells you the power of 3 in 2026!: it is (2026 − 6)/2 = 1010.

Answer: 5

1. (n + 12)/(n − 3) = 1 + 15/(n − 3), so n − 3 must divide 15.
2. n − 3 ∈ {1, 3, 5, 15, −1, −3, −5, −15}, giving n = 4, 6, 8, 18, 2, 0, −2, −12.
3. Positive values: 2, 4, 6, 8, 18: 5 numbers.

Why this works: Splitting off the whole-number part leaves a simple fraction whose denominator must divide its numerator. Remember negative divisors.

Where it leads: The same trick handles any (n + a)/(n + b): it is 1 + (a − b)/(n + b), so the number of solutions is controlled by the divisors of a − b.

Answer: A, 5

1. p² = 2q² + 1 is odd, so p is odd, and p² − 1 = (p − 1)(p + 1) is a product of two consecutive even numbers, so a multiple of 8.
2. So 2q² is a multiple of 8, so q² is a multiple of 4, so q is even: q = 2.
3. Then p² = 9 and p = 3, which is prime.
4. p + q = 5 (A).

Why this works: Parity, pushed one step further (multiples of 8), forces q to be the only even prime.

Where it leads: Without the prime condition, x² − 2y² = 1 has infinitely many solutions (3, 2), (17, 12), (99, 70), …: Pell’s equation, whose solutions approximate √2.

Answer: 50

1. T_n = n(n + 1)/2 is even exactly when n(n + 1) is a multiple of 4.
2. One of n, n + 1 is odd, so the other must be a multiple of 4: n ≡ 0 or 3 (mod 4).
3. The parities go odd, odd, even, even, odd, odd, even, even, … (period 4).
4. In 1 to 100 there are 25 complete blocks of 4, each with 2 even values: 50.

Why this works: Parity of a product of consecutive numbers depends only on n modulo 4, giving a repeating pattern.

Where it leads: Which triangle numbers are multiples of 3, or perfect squares? The square ones (1, 36, 1225, …) are linked to Pell’s equation again.