Difference between revisions of "2018 AIME I Problems/Problem 11"
m |
m (→Solution 7) |
||
Line 86: | Line 86: | ||
==Solution 7== | ==Solution 7== | ||
Note that the problem is basically asking for the least positive integer <math>n</math> such that <math>11^2 \cdot 13^2 | 3^n - 1.</math> It is easy to see that <math>n = \text{lcm } (a, b),</math> where <math>a</math> is the least positive integer satisfying <math>11^2 | 3^a - 1</math> and <math>b</math> the least positive integer satisfying <math>13^2 | 3^b - 1</math>. Luckily, finding <math>a</math> is a relatively trivial task, as one can simply notice that <math>3^5 = 243 \equiv 1 \mod 121</math>. However, finding <math>b</math> is slightly more nontrivial. The order of <math>3^k</math> modulo <math>13</math> (which is <math>3</math>) is trivial to find, as one can either bash out a pattern of remainders upon dividing powers of <math>3</math> by <math>13</math>, or one can notice that <math>3^3 = 27 \equiv 1 \mod 13</math> (the latter which is the definition of period/orders by FLT). We can thus rewrite <math>3^3</math> as <math>(2 \cdot 13 + 1) \mod 13^2</math>. Now suppose that <cmath>3^{3k} \equiv (13n + 1) \mod 13^2. </cmath> I claim that <math>3^{3(k+1)} \equiv (13(n+2) + 1) \mod 13^2. </math> | Note that the problem is basically asking for the least positive integer <math>n</math> such that <math>11^2 \cdot 13^2 | 3^n - 1.</math> It is easy to see that <math>n = \text{lcm } (a, b),</math> where <math>a</math> is the least positive integer satisfying <math>11^2 | 3^a - 1</math> and <math>b</math> the least positive integer satisfying <math>13^2 | 3^b - 1</math>. Luckily, finding <math>a</math> is a relatively trivial task, as one can simply notice that <math>3^5 = 243 \equiv 1 \mod 121</math>. However, finding <math>b</math> is slightly more nontrivial. The order of <math>3^k</math> modulo <math>13</math> (which is <math>3</math>) is trivial to find, as one can either bash out a pattern of remainders upon dividing powers of <math>3</math> by <math>13</math>, or one can notice that <math>3^3 = 27 \equiv 1 \mod 13</math> (the latter which is the definition of period/orders by FLT). We can thus rewrite <math>3^3</math> as <math>(2 \cdot 13 + 1) \mod 13^2</math>. Now suppose that <cmath>3^{3k} \equiv (13n + 1) \mod 13^2. </cmath> I claim that <math>3^{3(k+1)} \equiv (13(n+2) + 1) \mod 13^2. </math> | ||
− | [b]Proof:[/b] | + | <math>[b]Proof:[/b]</math> |
To find <math>3^{3(k+1)}, </math> we can simply multiply <math>3^{3k}</math> by <math>3^3, </math> which is congruent to <math>2 \cdot 13 + 1</math> modulo <math>13^2</math>. | To find <math>3^{3(k+1)}, </math> we can simply multiply <math>3^{3k}</math> by <math>3^3, </math> which is congruent to <math>2 \cdot 13 + 1</math> modulo <math>13^2</math>. | ||
By expanding the product out, we obtain <cmath>3^{3(k+1)} \equiv (13n + 1)(2 \cdot 13 + 1) = 13^2 \cdot 2n + 13n + 2 \cdot 13 + 1 \mod 13^2, </cmath> and since the <math>13^2</math> on the LHS cancels out, we're left with <cmath>13n + 2 \cdot 13 + 1 \mod 13^2 \implies 13(n+2) + 1 \mod 13^2</cmath>. Thus, our claim is proven. | By expanding the product out, we obtain <cmath>3^{3(k+1)} \equiv (13n + 1)(2 \cdot 13 + 1) = 13^2 \cdot 2n + 13n + 2 \cdot 13 + 1 \mod 13^2, </cmath> and since the <math>13^2</math> on the LHS cancels out, we're left with <cmath>13n + 2 \cdot 13 + 1 \mod 13^2 \implies 13(n+2) + 1 \mod 13^2</cmath>. Thus, our claim is proven. | ||
Line 94: | Line 94: | ||
-fidgetboss_4000 | -fidgetboss_4000 | ||
+ | -minor edits made by srisainandan6 | ||
==See Also== | ==See Also== | ||
{{AIME box|year=2018|n=I|num-b=10|num-a=12}} | {{AIME box|year=2018|n=I|num-b=10|num-a=12}} | ||
{{MAA Notice}} | {{MAA Notice}} |
Revision as of 14:45, 22 June 2020
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
Solution 7
Note that the problem is basically asking for the least positive integer such that
It is easy to see that
where
is the least positive integer satisfying
and
the least positive integer satisfying
. Luckily, finding
is a relatively trivial task, as one can simply notice that
. However, finding
is slightly more nontrivial. The order of
modulo
(which is
) is trivial to find, as one can either bash out a pattern of remainders upon dividing powers of
by
, or one can notice that
(the latter which is the definition of period/orders by FLT). We can thus rewrite
as
. Now suppose that
I claim that
To find
we can simply multiply
by
which is congruent to
modulo
.
By expanding the product out, we obtain
and since the
on the LHS cancels out, we're left with
. Thus, our claim is proven.
Let
be the second to last digit when
is written in base
.
Using our proof, it is easy to see that
satisfies the recurrence
and
. Since this implies
we just have to find the least positive integer
such that
is a multiple of
, which is trivially obtained as
.
The least integer
such that
is divisible by
is
so our final answer is
-fidgetboss_4000 -minor edits made by srisainandan6
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.