Difference between revisions of "1995 AIME Problems/Problem 8"
(expand) |
|||
| Line 15: | Line 15: | ||
[[Category:Intermediate Number Theory Problems]] | [[Category:Intermediate Number Theory Problems]] | ||
| + | {{MAA Notice}} | ||
Revision as of 18:30, 4 July 2013
Problem
For how many ordered pairs of positive integers 
with 
are both 
and 
integers?
Solution
Since 
, 
, then 
(the bars indicate divisibility) and 
. By the Euclidean algorithm, these can be rewritten respectively as 
and 
, which implies that both 
. Also, as 
, it follows that 
. [1]
Thus, for a given value of 
, we need the number of multiples of 
from 
to 
(as 
). It follows that there are 
satisfactory positive integers for all integers 
. The answer is
![\[\sum_{y=1}^{99} \left\lfloor\frac{100-y}{y(y+1)} \right\rfloor = 49 + 16 + 8 + 4 + 3 + 2 + 1 + 1 + 1 = \boxed{085}.\]](http://latex.artofproblemsolving.com/0/b/0/0b08a1c5231be8c3d8b6b09431be4f2db16f701b.png)
^ Another way of stating this is to note that if 
and are integers, then 
and 
must be integers. Since and 
cannot share common prime factors, it follows that 
must also be an integer.
See also
| 1995 AIME (Problems • Answer Key • Resources) | ||
| Preceded by Problem 7 |
Followed by Problem 9 | |
| 1 • 2 • 3 • 4 • 5 • 6 • 7 • 8 • 9 • 10 • 11 • 12 • 13 • 14 • 15 | ||
| All AIME Problems and Solutions | ||
The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions. 
