Difference between revisions of "2017 AIME I Problems/Problem 14"
R00tsofunity (talk | contribs) |
|||
Line 64: | Line 64: | ||
<cmath>2^{96} \equiv 656*656 \equiv 336\bmod 1000</cmath> | <cmath>2^{96} \equiv 656*656 \equiv 336\bmod 1000</cmath> | ||
<cmath>2^{192} \equiv 336*336 \equiv \boxed{896}\bmod 1000</cmath> | <cmath>2^{192} \equiv 336*336 \equiv \boxed{896}\bmod 1000</cmath> | ||
+ | |||
+ | ==Video Solution by mop 2024== | ||
+ | https://youtu.be/E-7YQ9ND5Ms | ||
+ | |||
+ | ~r00tsOfUnity | ||
== See also == | == See also == |
Revision as of 13:35, 7 August 2023
Problem 14
Let and
satisfy
and
. Find the remainder when
is divided by
.
Solution
The first condition implies
So .
Putting each side to the power of :
so . Specifically,
so we have that
We only wish to find . To do this, we note that
and now, by the Chinese Remainder Theorem, wish only to find
. By Euler's Theorem:
so
so we only need to find the inverse of . It is easy to realize that
, so
Using Chinese Remainder Theorem, we get that , finishing the solution.
Alternate solution
If you've found but you don't know that much number theory.
Note , so what we can do is take
and keep squaring it (mod 1000).
Video Solution by mop 2024
~r00tsOfUnity
See also
2017 AIME I (Problems • Answer Key • Resources) | ||
Preceded by Problem 13 |
Followed by Problem 15 | |
1 • 2 • 3 • 4 • 5 • 6 • 7 • 8 • 9 • 10 • 11 • 12 • 13 • 14 • 15 | ||
All AIME Problems and Solutions |
The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions.