Difference between revisions of "2018 AIME I Problems/Problem 11"

Revision as of 16:45, 23 November 2018

Problem

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 the given condition is equivalent to $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 $p_1 \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 (Big Bash)

Listing out the powers of $3$ , modulo $169$ and modulo $121$ , we have: $\begin{array}{c|c|c} n & 3^n\mod{169} & 3^n\mod{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 $\text{lcm}(5, 39) = \boxed{195}$ .

Solution 4(Order+Bash)

We have that $3^n \equiv 1 \pmod{143^2}.$ Now, $3^{110} \equiv 1 \pmod{11^2}$ so by the Fundamental Theorem of Orders, $\text{ord}_{11^2}(3)|110$ and with some bashing, we get that it is $5$ . Similarly, we get that $\text{ord}_{13^2}(3)=39$ . Now, $\text{lcm}(39,5)=\boxed{195}$ which is our desired solution.

Solution 5 (Easy Binomial Theorem)

We wish to find the smallest $n$ such that $3^n\equiv 1\pmod{143^2}$ , so we want $n\equiv 1\pmod{121}$ and $n\equiv \pmod{169}$ . Note that $3^5\equiv 1\pmod{121}$ , so $3^n$ repeats $121$ with a period of $5$ , so $5|n$ . Now, in order for $n\equiv 1\pmod{169}$ , then $n\equiv 1\pmod{13}$ . Because $3^3\equiv 1\pmod{13}$ , $3^n$ repeats with a period of $3$ , so $3|n$ . Hence, we have that for some positive integer $p$ , $3^n\equiv (3^3)^p\equiv (26+1)^p\equiv \binom{p}{0}26^p+\binom{p}{1}26^{p-1}....+binom{p}{p-2}26^2+\binom{p}{p-1}26+\binom{p}{p}\equiv 26p+1\equiv 1\pmod{169}$ , so $26p\equiv 0\pmod{169}$ and $p\equiv 0\pmod{13}$ . Thus, we have that $5|n$ , $3|n$ , and $13|n$ , so the smallest possible value of $n$ is $3\times5\times13=\boxed{195}$ . -Stormersyle

@@ Line 73: / Line 73: @@
 ==Solution 4(Order+Bash)==
 We have that <cmath>3^n \equiv 1 \pmod{143^2}.</cmath>Now, <math>3^{110} \equiv 1 \pmod{11^2}</math> so by the Fundamental Theorem of Orders, <math>\text{ord}_{11^2}(3)|110</math> and with some bashing, we get that it is <math>5</math>. Similarly, we get that <math>\text{ord}_{13^2}(3)=39</math>. Now, <math>\text{lcm}(39,5)=\boxed{195}</math> which is our desired solution.
+==Solution 5 (Easy Binomial Theorem)==
+We wish to find the smallest <math>n</math> such that <math>3^n\equiv 1\pmod{143^2}</math>, so we want <math>n\equiv 1\pmod{121}</math> and <math>n\equiv \pmod{169}</math>. Note that <math>3^5\equiv 1\pmod{121}</math>,  so <math>3^n</math> repeats <math>121</math> with a period of <math>5</math>, so <math>5|n</math>. Now, in order for <math>n\equiv 1\pmod{169}</math>, then <math>n\equiv 1\pmod{13}</math>. Because <math>3^3\equiv 1\pmod{13}</math>, <math>3^n</math> repeats with a period of <math>3</math>, so <math>3|n</math>.
+Hence, we have that for some positive integer <math>p</math>, <math>3^n\equiv (3^3)^p\equiv (26+1)^p\equiv \binom{p}{0}26^p+\binom{p}{1}26^{p-1}....+binom{p}{p-2}26^2+\binom{p}{p-1}26+\binom{p}{p}\equiv 26p+1\equiv 1\pmod{169}</math>, so <math>26p\equiv 0\pmod{169}</math> and <math>p\equiv 0\pmod{13}</math>. Thus, we have that <math>5|n</math>, <math>3|n</math>, and <math>13|n</math>, so the smallest possible value of <math>n</math> is <math>3\times5\times13=\boxed{195}</math>.
+-Stormersyle
 ==See Also==
 {{AIME box|year=2018|n=I|num-b=10|num-a=12}}
 {{MAA Notice}}

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

Page

Toolbox

Search