1995 AIME Problems/Problem 10
Problem
What is the largest positive integer that is not the sum of a positive integral multiple of 42 and a positive composite integer?
Solution
The requested number mod 42 must be a prime number. Also, every number that is a multiple of 42 greater than that prime number must also be prime, except for the requested number itself. So we make a table, listing all the primes up to 42 and the numbers that are multiples of 42 greater than them, until they reach a composite number.
2:44
3:45
5:47,89,131,173,215
7:49
11:53,95
13:55
17:59,101,143
19:61,103,145
23:65
29:71,113,155
31:73,115
37:79,121
41:83,125
215 is the greatest number in the list, so it is the answer.
