Difference between revisions of "2017 AIME I Problems/Problem 14"
(added problem and solution) |
m (→Solution 2 (Another way to find a)) |
||
(15 intermediate revisions by 7 users not shown) | |||
Line 1: | Line 1: | ||
− | ==Problem== | + | ==Problem 14== |
Let <math>a > 1</math> and <math>x > 1</math> satisfy <math>\log_a(\log_a(\log_a 2) + \log_a 24 - 128) = 128</math> and <math>\log_a(\log_a x) = 256</math>. Find the remainder when <math>x</math> is divided by <math>1000</math>. | Let <math>a > 1</math> and <math>x > 1</math> satisfy <math>\log_a(\log_a(\log_a 2) + \log_a 24 - 128) = 128</math> and <math>\log_a(\log_a x) = 256</math>. Find the remainder when <math>x</math> is divided by <math>1000</math>. | ||
− | ==Solution== | + | ==Solution 1== |
The first condition implies | The first condition implies | ||
Line 23: | Line 23: | ||
so <math>a^{128} = 64 \implies a = 2^{\frac{3}{64}}</math>. Specifically, | so <math>a^{128} = 64 \implies a = 2^{\frac{3}{64}}</math>. Specifically, | ||
− | <cmath>\log_a( | + | <cmath>\log_a(x) = \frac{\log_2(x)}{\log_2(a)} = \frac{64}{3}\log_2(x)</cmath> |
so we have that | so we have that | ||
− | <cmath>256 = \log_a(\log_a( | + | <cmath>256 = \log_a(\log_a(x)) = \frac{64}{3}\log_2\left(\frac{64}{3}\log_2(x)\right)</cmath> |
<cmath>12 = \log_2\left(\frac{64}{3}\log_2(x)\right)</cmath> | <cmath>12 = \log_2\left(\frac{64}{3}\log_2(x)\right)</cmath> | ||
− | <cmath>2^12 = \frac{64}{3}\log_2(x)</cmath> | + | <cmath>2^{12} = \frac{64}{3}\log_2(x)</cmath> |
<cmath>192 = \log_2(x)</cmath> | <cmath>192 = \log_2(x)</cmath> | ||
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 49: | Line 49: | ||
<cmath>x\equiv 21\bmod 125, x\equiv 0\bmod 8.</cmath> | <cmath>x\equiv 21\bmod 125, x\equiv 0\bmod 8.</cmath> | ||
− | Using | + | Using [[Chinese Remainder Theorem]], we get that <math>x\equiv \boxed{896}\bmod 1000</math>, finishing the solution. |
+ | |||
+ | ==Solution 2 (Another way to find a)== | ||
+ | |||
+ | <cmath>\log_a(\log_a(\log_a 2) + \log_a 24 - 128) = 128</cmath> | ||
+ | |||
+ | <cmath>\implies \log_a(\log_a 2))+\log_a(24)=a^{128}+128</cmath> | ||
+ | |||
+ | <cmath>\implies \log_a(\log_a 2^{24})=a^{128}+128</cmath> | ||
+ | |||
+ | <cmath>\implies 2^{24}=a^{a^{(a^{128}+128)}}</cmath> | ||
+ | |||
+ | Obviously letting <math>a=2^y</math> will simplify a lot and to make the <math>a^{128}</math> term simpler, let <math>a=2^{\frac{y}{128}}</math>. Then, | ||
+ | |||
+ | <cmath>2^{24}=2^{\frac{y}{128} \cdot 2^{\frac{y}{128} \cdot (2^y+128)}}=2^{\frac{y}{128} \cdot 2^{y \cdot (2^{y-7}+1)}}</cmath> | ||
+ | |||
+ | <cmath>\implies 24=\frac{y}{128} \cdot 2^{y \cdot (2^{y-7}+1)}</cmath> | ||
+ | |||
+ | <cmath>\implies 3 \cdot 2^{10}=y \cdot 2^{y \cdot (2^{y-7}+1)}</cmath> | ||
+ | |||
+ | Obviously, <math>y</math> is <math>3</math> times a power of <math>2</math>. 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 == | ||
+ | |||
+ | If you've found <math>x</math> but you don't know that much number theory. | ||
+ | |||
+ | Note <math>192 = 3 * 2^6</math>, so what we can do is take <math>2^3</math> and keep squaring it (mod 1000). | ||
+ | |||
+ | <cmath>2^3 = 8</cmath> | ||
+ | <cmath>2^6 = 8*8 = 64</cmath> | ||
+ | <cmath>2^{12} = 64*64 \equiv 96\bmod 1000</cmath> | ||
+ | <cmath>2^{24} \equiv 96*96 \equiv 216\bmod 1000</cmath> | ||
+ | <cmath>2^{48} \equiv 216*216 \equiv 656\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> | ||
+ | |||
+ | ==Video Solution by mop 2024== | ||
+ | https://youtu.be/E-7YQ9ND5Ms | ||
+ | |||
+ | ~r00tsOfUnity | ||
== See also == | == See also == | ||
{{AIME box|year=2017|n=I|num-b=13|num-a=15}} | {{AIME box|year=2017|n=I|num-b=13|num-a=15}} | ||
{{MAA Notice}} | {{MAA Notice}} | ||
+ | |||
+ | [[Category:Intermediate Algebra Problems]] | ||
+ | [[Category:Intermediate Number Theory Problems]] |
Latest revision as of 22:02, 29 June 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
. 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.