2020 CIME I Problems/Problem 7
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.