Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

Difference between revisions of "2017 AIME I Problems/Problem 14"

m (→‎Problem)
 
(16 intermediate revisions by 6 users not shown)
Line 3: Line 3:
 
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(y) = \frac{\log_2(y)}{\log_2(a)} = \frac{64}{3}\log_2(y)</cmath>
+
<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(y)) = \frac{64}{3}\log_2\left(\frac{64}{3}\log_2(x)\right)</cmath>
+
<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>
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 CRT, we get that <math>x\equiv \boxed{896}\bmod 1000</math>, finishing the solution.
+
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 1 ==
 +
 
 +
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>
 +
 
 +
== Alternate solution 2 ==
 +
 
 +
Another way to find <math>x \bmod 1000</math> using modular arithmetic.
 +
In the same way as solution <math>1</math>, we can find that.
 +
<cmath>x\equiv 21\bmod 125, x\equiv 0\bmod 8.</cmath>
 +
<cmath>x = 8m = 125n+21</cmath> For some positive integers <math>m</math> and <math>n</math>.
 +
Taking the equation mod <math>8</math> gives <cmath>5n+5 \equiv 0\bmod 8</cmath>
 +
<cmath>n \equiv 7\bmod 8</cmath>
 +
<cmath>n = 8k-1</cmath> For some positive integer <math>k</math>.
 +
Plug this back into the original equation.
 +
<cmath>8m = 125(8k-1)+21</cmath>
 +
<cmath>8m = 1000k-104</cmath>
 +
<cmath>x = 8m = 1000k - 104</cmath>
 +
<cmath>x \equiv -104 \equiv 896\bmod 1000</cmath>
 +
<cmath>x \equiv 896\bmod 1000</cmath>
 +
 
 +
~sdfgfjh
 +
==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 14:29, 8 September 2024

Problem 14

Let $a > 1$ and $x > 1$ satisfy $\log_a(\log_a(\log_a 2) + \log_a 24 - 128) = 128$ and $\log_a(\log_a x) = 256$. Find the remainder when $x$ is divided by $1000$.

Solution 1

The first condition implies

\[a^{128} = \log_a\log_a 2 + \log_a 24 - 128\]

\[128+a^{128} = \log_a\log_a 2^{24}\]

\[a^{a^{128}a^{a^{128}}} = 2^{24}\]

\[\left(a^{a^{128}}\right)^{\left(a^{a^{128}}\right)} = 2^{24} = 8^8\]

So $a^{a^{128}} = 8$.

Putting each side to the power of $128$:

\[\left(a^{128}\right)^{\left(a^{128}\right)} = 8^{128} = 64^{64},\]

so $a^{128} = 64 \implies a = 2^{\frac{3}{64}}$. Specifically,

\[\log_a(x) = \frac{\log_2(x)}{\log_2(a)} = \frac{64}{3}\log_2(x)\]

so we have that

\[256 = \log_a(\log_a(x)) = \frac{64}{3}\log_2\left(\frac{64}{3}\log_2(x)\right)\]

\[12 = \log_2\left(\frac{64}{3}\log_2(x)\right)\]

\[2^{12} = \frac{64}{3}\log_2(x)\]

\[192 = \log_2(x)\]

\[x = 2^{192}\]

We only wish to find $x\bmod 1000$. To do this, we note that $x\equiv 0\bmod 8$ and now, by the Chinese Remainder Theorem, wish only to find $x\bmod 125$. By Euler's Totient Theorem:

\[2^{\phi(125)} = 2^{100} \equiv 1\bmod 125\]

so

\[2^{192} \equiv \frac{1}{2^8} \equiv \frac{1}{256} \equiv \frac{1}{6} \bmod 125\]

so we only need to find the inverse of $6 \bmod 125$. It is easy to realize that $6\cdot 21 = 126 \equiv 1\bmod 125$, so

\[x\equiv 21\bmod 125, x\equiv 0\bmod 8.\]

Using Chinese Remainder Theorem, we get that $x\equiv \boxed{896}\bmod 1000$, finishing the solution.

Solution 2 (Another way to find a)

\[\log_a(\log_a(\log_a 2) + \log_a 24 - 128) = 128\]

\[\implies \log_a(\log_a 2))+\log_a(24)=a^{128}+128\]

\[\implies \log_a(\log_a 2^{24})=a^{128}+128\]

\[\implies 2^{24}=a^{a^{(a^{128}+128)}}\]

Obviously letting $a=2^y$ will simplify a lot and to make the $a^{128}$ term simpler, let $a=2^{\frac{y}{128}}$. Then,

\[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)}}\]

\[\implies 24=\frac{y}{128} \cdot 2^{y \cdot (2^{y-7}+1)}\]

\[\implies 3 \cdot 2^{10}=y \cdot 2^{y \cdot (2^{y-7}+1)}\]

Obviously, $y$ is $3$ times a power of $2$. Testing, we see $y=6$ satisfy the equation so $a=2^{\frac{3}{64}}$. Therefore, $x=2^{192} \equiv \boxed{896} \pmod{1000}$ ~Ddk001

Alternate solution 1

If you've found $x$ but you don't know that much number theory.

Note $192 = 3 * 2^6$, so what we can do is take $2^3$ and keep squaring it (mod 1000).

\[2^3 = 8\] \[2^6 = 8*8 = 64\] \[2^{12} = 64*64 \equiv 96\bmod 1000\] \[2^{24} \equiv 96*96 \equiv 216\bmod 1000\] \[2^{48} \equiv 216*216 \equiv 656\bmod 1000\] \[2^{96} \equiv 656*656 \equiv 336\bmod 1000\] \[2^{192} \equiv 336*336 \equiv \boxed{896}\bmod 1000\]

Alternate solution 2

Another way to find $x \bmod 1000$ using modular arithmetic. In the same way as solution $1$, we can find that. \[x\equiv 21\bmod 125, x\equiv 0\bmod 8.\] \[x = 8m = 125n+21\] For some positive integers $m$ and $n$. Taking the equation mod $8$ gives \[5n+5 \equiv 0\bmod 8\] \[n \equiv 7\bmod 8\] \[n = 8k-1\] For some positive integer $k$. Plug this back into the original equation. \[8m = 125(8k-1)+21\] \[8m = 1000k-104\] \[x = 8m = 1000k - 104\] \[x \equiv -104 \equiv 896\bmod 1000\] \[x \equiv 896\bmod 1000\]

~sdfgfjh

Video Solution by mop 2024

https://youtu.be/E-7YQ9ND5Ms

~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. AMC logo.png

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2017_AIME_I_Problems/Problem_14&oldid=226776"