Difference between revisions of "2020 CIME I Problems/Problem 7"
(→Solution) |
(→Solution) |
||
Line 3: | Line 3: | ||
==Solution== | ==Solution== | ||
− | Let <math>S(n) = f(1)+f(2)+\cdots+f(n)</math>. We claim that <cmath>S(n) = \frac{1}{2} - \frac{1}{2 \cdot (2n+1)!!}.</cmath> We show this using induction. Suppose this is true for some <math>n = k</math>. Then, it must be true for <math>k+1</math>. The base case when <math>k = 1</math> is trivial. Then, we have that <cmath>\begin{align*} S(k+1) &= f(k) + S(k) \\ {} &= \frac{n}{(2n+1)!!} + \frac{1}{2} - \frac{1}{2 \cdot (2n+1)!!} \\ {} &= \frac{1}{2} - \frac{1}{2 \cdot (2n+3)!!}. \end{align*}</cmath> Hence, this completes the induction therefore proving the claim. So, the numerator <math>p</math> is <math>\frac{1}{2}(4041!! - 1)</math>. We proceed using Euler's Theorem combined with Chinese Remainder Theorem. It is obvious that <math>4041!! \equiv 0 \pmod{125}</math> so <math>p \equiv 62\pmod{125}</math>. Also, instead of considering <math>p</math> modulo <math>8</math>, we consider it modulo <math>16</math>. Then, we get <cmath>4041!! \equiv 3^{253} \cdot 5^{253} \cdot 7^{253} \cdot 9^{252} \cdot 11^{252} \cdot 13^{252} \cdot 15^{252} \equiv 3 \cdot 5 \cdot 7 \cdot 9 \equiv 1\pmod{16},</cmath> by Euler's Totient Theorem as <math>\phi(16) = 8</math>. This implies that <math>\frac{1}{2}(4041!! - 1) \equiv 0\pmod{8}</math>, so <math>p \equiv 0\pmod{8}</math>. Solving the system of congruences, we get <math>p \equiv \boxed{312}\pmod{1000}</math>. ~rocketsri (based off of official solution) | + | Let <math>S(n) = f(1)+f(2)+\cdots+f(n)</math>. We claim that <cmath>S(n) = \frac{1}{2} - \frac{1}{2 \cdot (2n+1)!!}.</cmath> We show this using induction. Suppose this is true for some <math>n = k</math>. Then, it must be true for <math>k+1</math>. The base case when <math>k = 1</math> is trivial. Then, we have that <cmath>\begin{align*} S(k+1) &= f(k) + S(k) \\ {} &= \frac{n}{(2n+1)!!} + \frac{1}{2} - \frac{1}{2 \cdot (2n+1)!!} \\ {} &= \frac{1}{2} - \frac{1}{2 \cdot (2n+3)!!}. \end{align*}</cmath> Hence, this completes the induction therefore proving the claim. So, the numerator <math>p</math> is <math>\frac{1}{2}(4041!! - 1)</math>. |
+ | |||
+ | We proceed using Euler's Theorem combined with Chinese Remainder Theorem. It is obvious that <math>4041!! \equiv 0 \pmod{125}</math> so <math>p \equiv 62\pmod{125}</math>. Also, instead of considering <math>p</math> modulo <math>8</math>, we consider it modulo <math>16</math>. Then, we get <cmath>4041!! \equiv 3^{253} \cdot 5^{253} \cdot 7^{253} \cdot 9^{252} \cdot 11^{252} \cdot 13^{252} \cdot 15^{252} \equiv 3 \cdot 5 \cdot 7 \cdot 9 \equiv 1\pmod{16},</cmath> by Euler's Totient Theorem as <math>\phi(16) = 8</math>. This implies that <math>\frac{1}{2}(4041!! - 1) \equiv 0\pmod{8}</math>, so <math>p \equiv 0\pmod{8}</math>. Solving the system of congruences, we get <math>p \equiv \boxed{312}\pmod{1000}</math>. ~rocketsri (based off of official solution) | ||
==See also== | ==See also== |
Latest revision as of 12:05, 2 February 2021
Problem 7
For every positive integer , define Suppose that the sum can be expressed as for relatively prime integers and . Find the remainder when is divided by .
Solution
Let . We claim that We show this using induction. Suppose this is true for some . Then, it must be true for . The base case when is trivial. Then, we have that Hence, this completes the induction therefore proving the claim. So, the numerator is .
We proceed using Euler's Theorem combined with Chinese Remainder Theorem. It is obvious that so . Also, instead of considering modulo , we consider it modulo . Then, we get by Euler's Totient Theorem as . This implies that , so . Solving the system of congruences, we get . ~rocketsri (based off of official solution)
See also
2020 CIME I (Problems • Answer Key • Resources) | ||
Preceded by Problem 6 |
Followed by Problem 8 | |
1 • 2 • 3 • 4 • 5 • 6 • 7 • 8 • 9 • 10 • 11 • 12 • 13 • 14 • 15 | ||
All CIME Problems and Solutions |
The problems on this page are copyrighted by the MAC's Christmas Mathematics Competitions.