A friend recently posed me the following question: for an integer , how many pairs of positive integers exist for which
Call this number . Here is my solution. We will count the number of positive integers for which there exists a corresponding .
First, note that a exists if and only if the numerator of cancels when the fraction is put into lowest terms, in other words, if and only if .
Lemma 1: is equal to the number of integers for which , where denotes the greatest common divisor of and .
To see this fact, write and . Then . Since and are relatively prime, is relatively prime to both and , so , or
Lemma 2: is equal to the number of integers for which .
We will show that this set of s and the set of s given by Lemma 1 are in bijection. First, if , then clearly since is a divisor of .
Now suppose . Then is equal to a divisor of . We can write where and . Therefore both and divide the right-hand side and so divide , so both are common divisors of and and so and . Therefore .
Since for every divisor of we can solve for a unique , we have
Answer: , where the divisor function counts the number of positive divisors of . Note that this counts unordered pairs. There are unique ordered pairs with . For , there are 225 pairs (113 ordered pairs).
can be computed naively in by finding 's prime factorization using trial division. Possibly there are faster algorithms.
Footnote: Like the divisor function, is multiplicative: if , . Maybe there's a way to see that directly and use it to derive a formula for in an alternate way (by first finding a formula for when is a prime power.)