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 19:55, 5 April 2011
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 |