1995 AIME Problem 10

Attempt Problem 10 of the 1995 AIME below, then check your answer against the professionally curated solution from LIVE by Po-Shen Loh. You can also try the full timed exam, view all 1995 AIME solutions, or check the answer key.

All problems are used with official legal permission of the Mathematical Association of America (MAA).

10.

What is the largest positive integer that is not the sum of a positive integral multiple of 4242 and a positive composite integer?

Answer: 215
Concepts:modular arithmeticfactorextremal argument
Difficulty rating: 2110
Small Hint:

For each residue modulo 4242, find the smallest positive composite integer in that residue

Big Hint:

Once one number in a residue class is representable, every number 4242 larger in that class is representable

Solution:

A number in residue class r(mod42)r\pmod {42} is representable once it exceeds the first positive composite in that class by a positive multiple of 42.42. Composite residues rr themselves supply that first value. For the remaining residues, suitable first composites are 0:42, 1:85, 2:44,3:45, 5:215, 7:49,11:95, 13:55, 17:143,19:145, 23:65, 29:155,31:115, 37:121, 41:125.\begin{aligned}&0:42,\ 1:85,\ 2:44,\\&3:45,\ 5:215,\ 7:49,\\&11:95,\ 13:55,\ 17:143,\\&19:145,\ 23:65,\ 29:155,\\&31:115,\ 37:121,\ 41:125.\end{aligned} The largest entry is 215,215, and 21542,215-42, 21584,215-84, 215126,215-126, 215168,215-168, and 215210215-210 are all prime. Hence 215215 is not representable, while every larger integer is.

← Problem 9#9
Full Exam

Problem 10 in Other Years