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)
(minor edit/fix by Bigbrain_2009)
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.