Difference between revisions of "2018 AIME I Problems/Problem 11"
Tempaccount (talk | contribs) (Adding problem section) |
m (→Solution 3 (BigBash)) |
||
Line 23: | Line 23: | ||
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) | 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 ( | + | ==Solution 3 (Big Bash)== |
Listing out the powers of <math>3</math>, modulo <math>169</math> and modulo <math>121</math>, we have: | 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} | <cmath>\begin{array}{c|c|c} | ||
Line 69: | Line 69: | ||
\end{array}</cmath> | \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>. | + | 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>\text{lcm}(5, 39) = \boxed{195}</math>. |
==Solution 4(Order+Bash)== | ==Solution 4(Order+Bash)== |
Revision as of 02:48, 23 November 2018
Contents
Problem
Find the least positive integer such that when
is written in base
, its two right-most digits in base
are
.
Solutions
Modular Arithmetic Solution- Strange (MASS)
Note that the given condition is equivalent to and
. Because
, the desired condition is equivalent to
and
.
If , one can see the sequence
so
.
Now if , it is harder. But we do observe that
, therefore
for some integer
. So our goal is to find the first number
such that
. In other words, the
. It is not difficult to see that the smallest
, so ultimately
. Therefore,
.
The first satisfying both criteria is thus
.
-expiLnCalc
Solution 2
Note that Euler's Totient Theorem would not necessarily lead to the smallest and that in this case that
is greater than
.
We wish to find the least such that
. This factors as
. Because
, we can simply find the least
such that
and
.
Quick inspection yields and
. Now we must find the smallest
such that
. Euler's gives
. So
is a factor of
. This gives
. Some more inspection yields
is the smallest valid
. So
and
. The least
satisfying both is
. (RegularHexagon)
Solution 3 (Big Bash)
Listing out the powers of , modulo
and modulo
, we have:
The powers of repeat in cycles of
an
in modulo
and modulo
, respectively. The answer is
.
Solution 4(Order+Bash)
We have that Now,
so by the Fundamental Theorem of Orders,
and with some bashing, we get that it is
. Similarly, we get that
. Now,
which is our desired solution.
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.