Problem:
is an integer. Prove that the sum of all fractions , where and are relatively prime integers satisfying , , is .
Problem:
is an integer. Prove that the sum of all fractions , where and are relatively prime integers satisfying , , is .
Solution:
We use induction on . If , then the only such fraction is , , giving , so the result holds.
Suppose it holds for . As we move to , we lose the fractions with . The other fractions which satisfy the conditions for also satisfy the conditions for . We also gain the fractions with . These have sum (sum for all satisfying and relatively prime to ).
But if is relatively prime to , then so is , and does not equal (otherwise divides ). The pair , has sum . So the fractions with have sum equal to the sum of all with and relatively prime to . But that is exactly the sum of the fractions lost. Thus the total is unchanged as we move from to .