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.
Want a route through all this instead of an archive? The track
puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.