Difference between revisions of "1995 AIME Problems/Problem 10"
Dgreenb801 (talk | contribs) m (→Solution) |
(texing) |
||
| Line 1: | Line 1: | ||
== Problem == | == Problem == | ||
| − | What is the largest positive integer that is not the sum of a positive integral multiple of 42 and a positive composite integer? | + | What is the largest positive integer that is not the sum of a positive integral multiple of <math>42</math> and a positive composite integer? |
== Solution == | == 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. | + | The requested number <math>\mod {42}</math> must be a [[prime]] number. Also, every number that is a multiple of <math>42</math> 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 <math>42</math> and the numbers that are multiples of <math>42</math> greater than them, until they reach a composite number. |
| − | 2 | + | <cmath> |
| + | \begin{tabular}{|r||r|r|r|r|r|} | ||
| + | \hline | ||
| + | 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&&& \\ | ||
| + | \hline | ||
| + | \end{tabular}</cmath> | ||
| − | + | <math>\boxed{215}</math> is the greatest number in the list, so it is the answer. Note that considering <math>\mod {5}</math> would have shortened the search, since <math>\text{gcd}(5,42)=1</math>, and so within <math>5</math> numbers at least one must be divisible by <math>5</math>. | |
| − | + | == See also == | |
| − | + | {{AIME box|year=1995|num-b=9|num-a=11}} | |
| − | |||
| − | |||
| − | 11 | ||
| − | + | [[Category:Intermediate Number Theory Problems]] | |
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
Revision as of 20:50, 18 June 2008
Problem
What is the largest positive integer that is not the sum of a positive integral multiple of 
and a positive composite integer?
Solution
The requested number 
must be a prime number. Also, every number that is a multiple of 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 and the numbers that are multiples of greater than them, until they reach a composite number.
![\[\begin{tabular}{|r||r|r|r|r|r|} \hline 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&&& \\ \hline \end{tabular}\]](http://latex.artofproblemsolving.com/b/3/0/b300b2f4700c487eeca79b64f8b0792ef6475fdf.png)
is the greatest number in the list, so it is the answer. Note that considering 
would have shortened the search, since 
, and so within 
numbers at least one must be divisible by .
See also
| 1995 AIME (Problems • Answer Key • Resources) | ||
| Preceded by Problem 9 |
Followed by Problem 11 | |
| 1 • 2 • 3 • 4 • 5 • 6 • 7 • 8 • 9 • 10 • 11 • 12 • 13 • 14 • 15 | ||
| All AIME Problems and Solutions | ||
