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"

m (→‎Modular Arithmetic Solution- Strange (MASS))
(→‎Modular Arithmetic Solution- Strange (MASS))
Line 4: Line 4:
  
 
==Modular Arithmetic Solution- Strange (MASS)==
 
==Modular Arithmetic Solution- Strange (MASS)==
−
Note that <math>3^n \equiv 1 (\mod 143^2)</math>. And <math>143=11*13</math>. Because <math>gcd(11^2, 13^2) = 1</math>, <math>3^n \equiv 1 (\mod 121 = 11^2)</math> and <math>3^n \equiv 1 (\mod 169=13^2)</math>.
+
Note that <math>3^n \equiv 1 \pmod{143^2}</math> and <math>143=11\cdot 13</math>. Because <math>gcd(11^2, 13^2) = 1</math>, the desired condition is equivalent to <math>3^n \equiv 1 \pmod{121}</math> and <math>3^n \equiv 1 \pmod{169}</math>.
  
−
If <math>3^n \equiv 1 (\mod 121)</math>, one can see the sequence <math>1, 3, 9, 27, 81, 1, 3, 9...</math> so <math>5 \mid n</math>.
+
If <math>3^n \equiv 1 \pmod{121}</math>, one can see the sequence <math>1, 3, 9, 27, 81, 1, 3, 9...</math> so <math>5|n</math>.
  
−
Now if <math>3^n \equiv 1 (\mod 169)</math>, it is harder. But we do observe that <math>3^3 \equiv 1 (\mod 13)</math>, therefore <math>3^3 = 13a + 1</math> for some integer <math>a</math>. So our goal is to find the first number <math>p_1</math> such that <math>(13a+1)^ {p_1} \equiv 1 (\mod 169)</math>. In other words, the <math>a</math> coefficient must be <math>0 (\mod 169)</math>. It is not difficult to see that this first <math>p_1=13</math>, so ultimately <math>3^{39} \equiv 1 (\mod 169)</math>. Therefore, <math>39 \mid n</math>.
+
Now if <math>3^n \equiv 1 \pmod{169}</math>, it is harder. But we do observe that <math>3^3 \equiv 1 \pmod{13}</math>, therefore <math>3^3 = 13a + 1</math> for some integer <math>a</math>. So our goal is to find the first number <math>p_1</math> such that <math>(13a+1)^ {p_1} \equiv 1 \pmod{169}</math>. In other words, the <math>a \equiv 0 \pmod{13}</math>. It is not difficult to see that the smallest <math>p_1=13</math>, so ultimately <math>3^{39} \equiv 1 \pmod{169}</math>. Therefore, <math>39|n</math>.
  
−
The first <math>n</math> satisfying both criteria is <math>5*39=\boxed{195}</math>.
+
The first <math>n</math> satisfying both criteria is thus <math>5\cdot 39=\boxed{195}</math>.
  
 
-expiLnCalc
 
-expiLnCalc

Revision as of 21:46, 16 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

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(\mod 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(\mod 121)$ and $3^n \equiv 1(\mod 169)$.

Quick inspection yields $3^5 \equiv 1(\mod 121)$ and $3^3 \equiv 1(\mod 13)$. Now we must find the smallest $k$ such that $3^{3k} \equiv 1(\mod 13)$. Euler's gives $3^{156} \equiv 1(\mod 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(\mod 121)$ and $3^{39} \equiv 1(\mod 169)$. The least $n$ satisfying both is $lcm[5,39]=\boxed{195}$. (RegularHexagon)

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=93295"