2017 AIME I Problems/Problem 14
Contents
[hide]Problem 14
Let and satisfy and . Find the remainder when is divided by .
Solution 1
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 Totient 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.
Solution 2 (Another way to find a)
Obviously letting will simplify a lot and to make the term simpler, let . Then,
Obviously, is times a power of . Testing, we see satisfy the equation so . Therefore, ~Ddk001
Alternate solution 1
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).
Alternate solution 2
Another way to find using modular arithmetic. In the same way as solution , we can find that. For some positive integers and . Taking the equation mod gives For some positive integer . Plug this back into the original equation.
~sdfgfjh
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.