Difference between revisions of "2010 USAMO Problems/Problem 5"
(→Alternative Calculation) |
(Added to olympiad number theory category) |
||
(3 intermediate revisions by 3 users not shown) | |||
Line 50: | Line 50: | ||
\begin{align*} | \begin{align*} | ||
\frac{1}{p} - 2S_q | \frac{1}{p} - 2S_q | ||
− | &= \frac{1}{2r+1} - \left(\sum_{k= | + | &= \frac{1}{2r+1} - \left(\sum_{k=2}^{3r+1}\frac{1}{k} - \sum_{k=1}^{r} \frac{1}{k}\right) \\ |
&= \frac{1}{2r+1} - \left(\sum_{k=r+1}^{3r+1}\frac{1}{k} - 1\right) \\ | &= \frac{1}{2r+1} - \left(\sum_{k=r+1}^{3r+1}\frac{1}{k} - 1\right) \\ | ||
&= 1 - \left(\sum_{k=r+1}^{2r}\frac{1}{k} + \sum_{k=2r+2}^{3r+1}\frac{1}{k}\right) | &= 1 - \left(\sum_{k=r+1}^{2r}\frac{1}{k} + \sum_{k=2r+2}^{3r+1}\frac{1}{k}\right) | ||
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}} | ||
+ | [[Category:Olympiad Number Theory Problems]] | ||
+ | {{MAA Notice}} |
Latest revision as of 01:08, 15 June 2020
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 |
The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions.