1995 AIME Problems/Problem 8
Contents
Problem
For how many ordered pairs of positive integers with are both and integers?
Solution 1
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.
Solution 2
We know that and .
Write as for some integer . Then, . We can add to each side in order to factor out a . So, or . We know that . We finally achieve the congruence .
We can now write as . Plugging this back in, if we have a value for , then . We only have to check values of when . This yields the equations .
Finding all possible values of such that , we get
Solution 3 (Rigorous, but straightforward)
We use casework:
For , we have , or cases.
For , we have , or cases.
For , we have , or cases.
For , we have , or cases.
For , we have , or cases.
For , we have , or cases.
For , we have , or case.
For , we have , or case.
For , we have , or case.
Adding, we get our final result of
Note: In general, all of the solutions for all are , for any such that
~SirAppel
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.