Difference between revisions of "2018 AIME I Problems/Problem 11"
Bradleyguo (talk | contribs) (→Solution 6(LTE)) |
Bradleyguo (talk | contribs) (→Solution 6(LTE)) |
||
Line 80: | Line 80: | ||
==Solution 6(LTE)== | ==Solution 6(LTE)== | ||
− | We can see that <math>3^n-1 = 143^2*x</math>, which means that <math>v_{11}(3^n-1) \geq 2</math>, <math>v_{13}(3^n-1) \geq 2</math>. <math>v_{11}(3^n-1) = v_{11}(242) + v_{11}(\frac{n}{5})</math>, <math>v_{13}(3^n-1) = v_{13}(26) + v_{13}(\frac{n}{3})</math> by the Lifting the Exponent lemma. From the first equation we gather that 5 divides n, while from the second equation we gather that both 13 and 3 divide n as <math>v_{13}(3^n-1) | + | We can see that <math>3^n-1 = 143^2*x</math>, which means that <math>v_{11}(3^n-1) \geq 2</math>, <math>v_{13}(3^n-1) \geq 2</math>. <math>v_{11}(3^n-1) = v_{11}(242) + v_{11}(\frac{n}{5})</math>, <math>v_{13}(3^n-1) = v_{13}(26) + v_{13}(\frac{n}{3})</math> by the Lifting the Exponent lemma. From the first equation we gather that 5 divides n, while from the second equation we gather that both 13 and 3 divide n as <math>v_{13}(3^n-1) \geq 2</math>. Therefore the minimum possible value of n is <math>3\times5\times13=\boxed{195}</math>. |
-bradleyguo | -bradleyguo |
Revision as of 17:27, 22 August 2019
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.
Solution 5 (Easy Binomial Theorem)
We wish to find the smallest such that
, so we want
and
. Note that
, so
repeats
with a period of
, so
. Now, in order for
, then
. Because
,
repeats with a period of
, so
.
Hence, we have that for some positive integer
,
, so
and
. Thus, we have that
,
, and
, so the smallest possible value of
is
.
-Stormersyle
Solution 6(LTE)
We can see that , which means that
,
.
,
by the Lifting the Exponent lemma. From the first equation we gather that 5 divides n, while from the second equation we gather that both 13 and 3 divide n as
. Therefore the minimum possible value of n is
.
-bradleyguo
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.