1995 AIME Problems/Problem 8
For how many ordered pairs of positive integers with are both and integers?
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.
We know that and .
Write and 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
|1995 AIME (Problems • Answer Key • Resources)|
|1 • 2 • 3 • 4 • 5 • 6 • 7 • 8 • 9 • 10 • 11 • 12 • 13 • 14 • 15|
|All AIME Problems and Solutions|