Difference between revisions of "2017 AIME I Problems/Problem 14"
m (→Solution 2 (Another way to find a)) |
m (→Solution 2 (Another way to find a)) |
||
(2 intermediate revisions by the same user not shown) | |||
Line 37: | Line 37: | ||
<cmath>x = 2^{192}</cmath> | <cmath>x = 2^{192}</cmath> | ||
− | We only wish to find <math>x\bmod 1000</math>. To do this, we note that <math>x\equiv 0\bmod 8</math> and now, by the Chinese Remainder Theorem, wish only to find <math>x\bmod 125</math>. By Euler's Theorem: | + | We only wish to find <math>x\bmod 1000</math>. To do this, we note that <math>x\equiv 0\bmod 8</math> and now, by the Chinese Remainder Theorem, wish only to find <math>x\bmod 125</math>. By [[Euler's Totient Theorem]]: |
<cmath>2^{\phi(125)} = 2^{100} \equiv 1\bmod 125</cmath> | <cmath>2^{\phi(125)} = 2^{100} \equiv 1\bmod 125</cmath> | ||
Line 55: | Line 55: | ||
<math>\log_a(\log_a(\log_a 2) + \log_a 24 - 128) = 128</math> | <math>\log_a(\log_a(\log_a 2) + \log_a 24 - 128) = 128</math> | ||
− | <math>\implies \log_a(\log_a 2))+log_a(24)=a^{128}+128</math> | + | <math>\implies \log_a(\log_a 2))+\log_a(24)=a^{128}+128</math> |
<math>\implies \log_a(\log_a 2^{24})=a^{128}+128</math> | <math>\implies \log_a(\log_a 2^{24})=a^{128}+128</math> | ||
Line 69: | Line 69: | ||
<math>\implies 3 \cdot 2^{10}=y \cdot 2^{y \cdot (2^{y-7}+1)}</math> | <math>\implies 3 \cdot 2^{10}=y \cdot 2^{y \cdot (2^{y-7}+1)}</math> | ||
− | Obviously, y is <math>3</math> times a power of <math>2</math>. (It just makes sense.) Testing, we see <math>y=6</math> satisfy the equation so <math>a=2^{\frac{3}{64}}</math>. Therefore, <math>x=2^{192} \equiv \boxed{896} \pmod{1000}</math> ~[[Ddk001]] | + | Obviously, <math>y</math> is <math>3</math> times a power of <math>2</math>. (It just makes sense.) Testing, we see <math>y=6</math> satisfy the equation so <math>a=2^{\frac{3}{64}}</math>. Therefore, <math>x=2^{192} \equiv \boxed{896} \pmod{1000}</math> ~[[Ddk001]] |
== Alternate solution == | == Alternate solution == |
Latest revision as of 14:35, 3 January 2024
Contents
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 . (It just makes sense.) Testing, we see satisfy the equation so . Therefore, ~Ddk001
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.