Difference between revisions of "2018 AIME I Problems/Problem 11"
m (→Modular Arithmetic Solution- Strange (MASS))
|Line 96:||Line 96:|
-minor edits made by srisainandan6
-minor edits made by srisainandan6
Revision as of 12:01, 30 December 2020
Find the least positive integer such that when is written in base , its two right-most digits in base are .
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 .
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 .
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
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 .
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
Proof: 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
|2018 AIME I (Problems • Answer Key • Resources)|
|1 • 2 • 3 • 4 • 5 • 6 • 7 • 8 • 9 • 10 • 11 • 12 • 13 • 14 • 15|
|All AIME Problems and Solutions|