1995 AIME Problems/Problem 10

From AoPSWiki

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.

$\begin{tabular}{|r||r|r|r|r|r|}\hline2&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&&& \\\hline\end{tabular}$

$\boxed{215}$ is the greatest number in the list, so it is the answer. Note that considering $\mod {5}$ would have shortened the search, since $\text{gcd}(5,42)=1$ , and so within $5$ numbers at least one must be divisible by $5$ .

1995 AIME (Problems • Resources)
Preceded by Problem 9	Followed by Problem 11
1 • 2 • 3 • 4 • 5 • 6 • 7 • 8 • 9 • 10 • 11 • 12 • 13 • 14 • 15

Personal tools

Navigation

Search

Toolbox

1995 AIME Problems/Problem 10

From AoPSWiki

Problem

Solution

See also