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 "2018 AIME I Problems/Problem 11"

(→‎Modular Arithmetic Solution- Strange (MASS))
(→‎Solution)
Line 14: Line 14:
 
-expiLnCalc
 
-expiLnCalc
  
−
==Solution==
+
==Solution 2==
 
Note that Euler's Totient Theorem would not necessarily lead to the smallest <math>n</math> and that in this case that <math>n</math> is greater than <math>1000</math>.  
 
Note that Euler's Totient Theorem would not necessarily lead to the smallest <math>n</math> and that in this case that <math>n</math> is greater than <math>1000</math>.  
  
−
We wish to find the least <math>n</math> such that <math>3^n \equiv 1(\mod 143^2)</math>. This factors as <math>143^2=11^{2}*13^{2}</math>. Because <math>gcd(121, 169) = 1</math>, we can simply find the least  <math>n</math> such that <math>3^n \equiv 1(\mod 121)</math> and <math>3^n \equiv 1(\mod 169)</math>.
+
We wish to find the least <math>n</math> such that <math>3^n \equiv 1 \pmod{143^2}</math>. This factors as <math>143^2=11^{2}*13^{2}</math>. Because <math>gcd(121, 169) = 1</math>, we can simply find the least  <math>n</math> such that <math>3^n \equiv 1 \pmod{121}</math> and <math>3^n \equiv 1 \pmod{169}</math>.
  
−
Quick inspection yields <math>3^5 \equiv 1(\mod 121)</math> and <math>3^3 \equiv 1(\mod 13)</math>. Now we must find the smallest <math>k</math> such that <math>3^{3k} \equiv 1(\mod 13)</math>. Euler's gives <math>3^{156} \equiv 1(\mod 169)</math>. So <math>3k</math> is a factor of <math>156</math>. This gives <math>k=1,2, 4, 13, 26, 52</math>. Some more inspection yields <math>k=13</math> is the smallest valid <math>k</math>. So <math>3^5 \equiv 1(\mod 121)</math> and <math>3^{39} \equiv 1(\mod 169)</math>. The least <math>n</math> satisfying both is <math>lcm[5,39]=\boxed{195}</math>. (RegularHexagon)
+
Quick inspection yields <math>3^5 \equiv 1 \pmod{121}</math> and <math>3^3 \equiv 1 \pmod{13}</math>. Now we must find the smallest <math>k</math> such that <math>3^{3k} \equiv 1 \pmod{13}</math>. Euler's gives <math>3^{156} \equiv 1 \pmod{169}</math>. So <math>3k</math> is a factor of <math>156</math>. This gives <math>k=1,2, 4, 13, 26, 52</math>. Some more inspection yields <math>k=13</math> is the smallest valid <math>k</math>. So <math>3^5 \equiv 1 \pmod{121}</math> and <math>3^{39} \equiv 1 \pmod{169}</math>. The least <math>n</math> satisfying both is <math>lcm(5, 39)=\boxed{195}</math>. (RegularHexagon)
 +
 
 +
==Solution 3==
 +
Listing out the powers of <math>3</math>, modulo <math>169</math> and modulo <math>121</math>, we have:
 +
<cmath>\begin{array}{c|c|c}
 +
n & 3^n\pmod{169} & 3^n\pmod{121}\\ \hline
 +
0 & 1 & 1\\
 +
1 & 3 & 3\\
 +
2 & 9 & 9\\
 +
3 & 27 & 27\\
 +
4 & 81 & 81\\
 +
5 & 74 & 1\\
 +
6 & 53\\
 +
7 & 159\\
 +
8 & 139\\
 +
9 & 79\\
 +
10 & 68\\
 +
11 & 35\\
 +
12 & 105\\
 +
13 & 146\\
 +
14 & 100\\
 +
15 & 131\\
 +
16 & 55\\
 +
17 & 165\\
 +
18 & 157\\
 +
19 & 133\\
 +
20 & 61\\
 +
21 & 14\\
 +
22 & 42\\
 +
23 & 126\\
 +
24 & 40\\
 +
25 & 120\\
 +
26 & 22\\
 +
27 & 66\\
 +
28 & 29\\
 +
29 & 87\\
 +
30 & 92\\
 +
31 & 107\\
 +
32 & 152\\
 +
33 & 118\\
 +
34 & 16\\
 +
35 & 48\\
 +
36 & 144\\
 +
37 & 94\\
 +
38 & 113\\
 +
39 & 1\\
 +
\end{array}</cmath>
 +
 
 +
The powers of <math>3</math> repeat in cycles of <math>5</math> an <math>39</math> in modulo <math>121</math> and modulo <math>169</math>, respectively. The answer is <math>lcm(5, 39) = \boxed{195}</math>
  
 
==See Also==
 
==See Also==
 
{{AIME box|year=2018|n=I|num-b=10|num-a=12}}
 
{{AIME box|year=2018|n=I|num-b=10|num-a=12}}
 
{{MAA Notice}}
 
{{MAA Notice}}

Revision as of 18:04, 26 March 2018

Find the least positive integer $n$ such that when $3^n$ is written in base $143$, its two right-most digits in base $143$ are $01$.

Solutions

Modular Arithmetic Solution- Strange (MASS)

Note that $3^n \equiv 1 \pmod{143^2}$ and $143=11\cdot 13$. Because $gcd(11^2, 13^2) = 1$, the desired condition is equivalent to $3^n \equiv 1 \pmod{121}$ and $3^n \equiv 1 \pmod{169}$.

If $3^n \equiv 1 \pmod{121}$, one can see the sequence $1, 3, 9, 27, 81, 1, 3, 9...$ so $5|n$.

Now if $3^n \equiv 1 \pmod{169}$, it is harder. But we do observe that $3^3 \equiv 1 \pmod{13}$, therefore $3^3 = 13a + 1$ for some integer $a$. So our goal is to find the first number $p_1$ such that $(13a+1)^ {p_1} \equiv 1 \pmod{169}$. In other words, the $a \equiv 0 \pmod{13}$. It is not difficult to see that the smallest $p_1=13$, so ultimately $3^{39} \equiv 1 \pmod{169}$. Therefore, $39|n$.

The first $n$ satisfying both criteria is thus $5\cdot 39=\boxed{195}$.

-expiLnCalc

Solution 2

Note that Euler's Totient Theorem would not necessarily lead to the smallest $n$ and that in this case that $n$ is greater than $1000$.

We wish to find the least $n$ such that $3^n \equiv 1 \pmod{143^2}$. This factors as $143^2=11^{2}*13^{2}$. Because $gcd(121, 169) = 1$, we can simply find the least $n$ such that $3^n \equiv 1 \pmod{121}$ and $3^n \equiv 1 \pmod{169}$.

Quick inspection yields $3^5 \equiv 1 \pmod{121}$ and $3^3 \equiv 1 \pmod{13}$. Now we must find the smallest $k$ such that $3^{3k} \equiv 1 \pmod{13}$. Euler's gives $3^{156} \equiv 1 \pmod{169}$. So $3k$ is a factor of $156$. This gives $k=1,2, 4, 13, 26, 52$. Some more inspection yields $k=13$ is the smallest valid $k$. So $3^5 \equiv 1 \pmod{121}$ and $3^{39} \equiv 1 \pmod{169}$. The least $n$ satisfying both is $lcm(5, 39)=\boxed{195}$. (RegularHexagon)

Solution 3

Listing out the powers of $3$, modulo $169$ and modulo $121$, we have: \[\begin{array}{c|c|c} n & 3^n\pmod{169} & 3^n\pmod{121}\\ \hline 0 & 1 & 1\\ 1 & 3 & 3\\ 2 & 9 & 9\\ 3 & 27 & 27\\ 4 & 81 & 81\\ 5 & 74 & 1\\ 6 & 53\\ 7 & 159\\ 8 & 139\\ 9 & 79\\ 10 & 68\\ 11 & 35\\ 12 & 105\\ 13 & 146\\ 14 & 100\\ 15 & 131\\ 16 & 55\\ 17 & 165\\ 18 & 157\\ 19 & 133\\ 20 & 61\\ 21 & 14\\ 22 & 42\\ 23 & 126\\ 24 & 40\\ 25 & 120\\ 26 & 22\\ 27 & 66\\ 28 & 29\\ 29 & 87\\ 30 & 92\\ 31 & 107\\ 32 & 152\\ 33 & 118\\ 34 & 16\\ 35 & 48\\ 36 & 144\\ 37 & 94\\ 38 & 113\\ 39 & 1\\ \end{array}\]

The powers of $3$ repeat in cycles of $5$ an $39$ in modulo $121$ and modulo $169$, respectively. The answer is $lcm(5, 39) = \boxed{195}$

See Also

2018 AIME I (Problems • Answer Key • Resources)
Preceded by
Problem 10 		Followed by
Problem 12
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=2018_AIME_I_Problems/Problem_11&oldid=93522"