Problem:
Find the sum of all positive rational numbers that are less than and that have denominator when written in lowest terms.
Solution:
A positive rational number that is less than and has denominator can be written in the form
where and are integers satisfying and . Furthermore, such a fraction is in lowest terms if and only if and are relatively prime; i.e., if and only if . Thus there are choices for and choices for , and no two pairs of choices give the same value of . It follows that the desired sum has terms. These may be paired by noting that is one of these fractions if and only if is as well. Since the sum of each of these pairs is , we find that the sum of all such fractions is
The problems on this page are the property of the MAA's American Mathematics Competitions