Difference between revisions of "2018 AIME I Problems/Problem 11"
Expilncalc (talk | contribs) (Wrote solution page.) |
Expilncalc (talk | contribs) m (→Modular Arithmetic Solution- Strange (MASS)) |
||
Line 8: | Line 8: | ||
If <math>3^n \cong 1 (\mod 121)</math>, one can see the sequence <math>1, 3, 9, 27, 81, 1, 3, 9...</math> so <math>n \mid 5</math>. | If <math>3^n \cong 1 (\mod 121)</math>, one can see the sequence <math>1, 3, 9, 27, 81, 1, 3, 9...</math> so <math>n \mid 5</math>. | ||
− | Now if <math>3^n \cong 1 (\mod 169)</math>, it is harder. But we do observe that <math>3^3 \cong 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)^ | + | Now if <math>3^n \cong 1 (\mod 169)</math>, it is harder. But we do observe that <math>3^3 \cong 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} \cong 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 \cong 1 (\mod 169)</math>. Therefore, <math>n \mid 39</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 <math>5*39=\boxed{195}</math>. | ||
-expiLnCalc | -expiLnCalc |
Revision as of 18:44, 7 March 2018
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 . And
. Because
,
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
coefficient must be
. It is not difficult to see that this first
, so ultimately
. Therefore,
.
The first satisfying both criteria is
.
-expiLnCalc