2010 USAMO Problems/Problem 5
Problem
Let where is an odd prime, and let
Prove that if for integers and , then is divisible by .
Solution
Since is an odd prime, , for a suitable positive integer , and consequently .
The partial-fraction decomposition of the general term of is:
therefore
with and positive relatively-prime integers.
Since and is a prime, in the final sum all the denominators are relatively prime to , but all the numerators are divisible by , and therefore the numerator of the reduced fraction will be divisible by . Since the sought difference , we conclude that divides as required.
Alternative Calculation
We can obtain the result in a slightly different way:
In the above sum the denominators of the fractions represent each non-zero remainder exactly once. Multiplying all the denominators yields a number that is . The numerator is times the sum of the inverses of each non-zero remainder, and since this sum is , the numerator is . The rest of the argument is as before.