Difference between revisions of "2010 USAMO Problems/Problem 5"
(→Alternative Calculation) |
m (Added USAMO box.) |
||
Line 57: | Line 57: | ||
</center> | </center> | ||
In the above sum the denominators of the fractions represent each non-zero remainder <math>\pmod p</math> exactly once. Multiplying all the denominators yields a number <math>N</math> that is <math>p-1 \pmod p</math>. The numerator <math>\pmod p</math> is <math>N</math> times the sum of the <math>\pmod p</math> inverses of each non-zero remainder, and since this sum is <math>0 \pmod p</math>, the numerator is <math>0 \pmod p</math>. The rest of the argument is as before. | In the above sum the denominators of the fractions represent each non-zero remainder <math>\pmod p</math> exactly once. Multiplying all the denominators yields a number <math>N</math> that is <math>p-1 \pmod p</math>. The numerator <math>\pmod p</math> is <math>N</math> times the sum of the <math>\pmod p</math> inverses of each non-zero remainder, and since this sum is <math>0 \pmod p</math>, the numerator is <math>0 \pmod p</math>. The rest of the argument is as before. | ||
+ | |||
+ | ==See also== | ||
+ | {{USAMO newbox|year=2010|num-b=4|num-a=6}} |
Revision as of 18:55, 5 April 2011
Contents
[hide]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.
See also
2010 USAMO (Problems • Resources) | ||
Preceded by Problem 4 |
Followed by Problem 6 | |
1 • 2 • 3 • 4 • 5 • 6 | ||
All USAMO Problems and Solutions |