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 19: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
^ 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.