Difference between revisions of "2018 AIME I Problems/Problem 11"
Stormersyle (talk | contribs) |
Stormersyle (talk | contribs) |
||
Line 76: | Line 76: | ||
==Solution 5 (Easy Binomial Theorem)== | ==Solution 5 (Easy Binomial Theorem)== | ||
We wish to find the smallest <math>n</math> such that <math>3^n\equiv 1\pmod{143^2}</math>, so we want <math>n\equiv 1\pmod{121}</math> and <math>n\equiv \pmod{169}</math>. Note that <math>3^5\equiv 1\pmod{121}</math>, so <math>3^n</math> repeats <math>121</math> with a period of <math>5</math>, so <math>5|n</math>. Now, in order for <math>n\equiv 1\pmod{169}</math>, then <math>n\equiv 1\pmod{13}</math>. Because <math>3^3\equiv 1\pmod{13}</math>, <math>3^n</math> repeats with a period of <math>3</math>, so <math>3|n</math>. | We wish to find the smallest <math>n</math> such that <math>3^n\equiv 1\pmod{143^2}</math>, so we want <math>n\equiv 1\pmod{121}</math> and <math>n\equiv \pmod{169}</math>. Note that <math>3^5\equiv 1\pmod{121}</math>, so <math>3^n</math> repeats <math>121</math> with a period of <math>5</math>, so <math>5|n</math>. Now, in order for <math>n\equiv 1\pmod{169}</math>, then <math>n\equiv 1\pmod{13}</math>. Because <math>3^3\equiv 1\pmod{13}</math>, <math>3^n</math> repeats with a period of <math>3</math>, so <math>3|n</math>. | ||
− | Hence, we have that for some positive integer <math>p</math>, <math>3^n\equiv (3^3)^p\equiv (26+1)^p\equiv \binom{p}{0}26^p+\binom{p}{1}26^{p-1}....+binom{p}{p-2}26^2+\binom{p}{p-1}26+\binom{p}{p}\equiv 26p+1\equiv 1\pmod{169}</math>, so <math>26p\equiv 0\pmod{169}</math> and <math>p\equiv 0\pmod{13}</math>. Thus, we have that <math>5|n</math>, <math>3|n</math>, and <math>13|n</math>, so the smallest possible value of <math>n</math> is <math>3\times5\times13=\boxed{195}</math>. | + | Hence, we have that for some positive integer <math>p</math>, <math>3^n\equiv (3^3)^p\equiv (26+1)^p\equiv \binom{p}{0}26^p+\binom{p}{1}26^{p-1}....+\binom{p}{p-2}26^2+\binom{p}{p-1}26+\binom{p}{p}\equiv 26p+1\equiv 1\pmod{169}</math>, so <math>26p\equiv 0\pmod{169}</math> and <math>p\equiv 0\pmod{13}</math>. Thus, we have that <math>5|n</math>, <math>3|n</math>, and <math>13|n</math>, so the smallest possible value of <math>n</math> is <math>3\times5\times13=\boxed{195}</math>. |
-Stormersyle | -Stormersyle | ||
Revision as of 16:47, 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.
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
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.