Difference between revisions of "2018 AIME I Problems/Problem 11"
Elephant353 (talk | contribs) m (→Solution) |
m (→Solution) |
||
Line 19: | Line 19: | ||
We wish to find the least <math>n</math> such that <math>3^n \equiv 1(\mod 143^2)</math>. This factors as <math>143^2=11^{2}*13^{2}</math>. Because <math>gcd(121, 169) = 1</math>, we can simply find the least <math>n</math> such that <math>3^n \equiv 1(\mod 121)</math> and <math>3^n \equiv 1(\mod 169)</math>. | We wish to find the least <math>n</math> such that <math>3^n \equiv 1(\mod 143^2)</math>. This factors as <math>143^2=11^{2}*13^{2}</math>. Because <math>gcd(121, 169) = 1</math>, we can simply find the least <math>n</math> such that <math>3^n \equiv 1(\mod 121)</math> and <math>3^n \equiv 1(\mod 169)</math>. | ||
− | Quick inspection yields <math>3^5 \equiv 1(\mod 121)</math> and <math>3^3 \equiv 1(\mod 13)</math>. Now we must find the smallest <math>k</math> such that <math>3^3k \equiv 1(\mod 13)</math>. Euler's gives <math>3^156 \equiv 1(\mod 169)</math>. So <math>3k</math> is a factor of <math>156</math>. This gives <math>k=2, 4, 13, 26, 52</math>. Some more inspection yields <math>k=13</math> is the smallest valid <math>k</math>. So <math>3^5 \equiv 1(\mod 121)</math> and <math>3^39 \equiv 1(\mod 169)</math>. The least <math>n</math> satisfying both is <math>lcm[5,39]=\boxed{195}</math>. (RegularHexagon) | + | Quick inspection yields <math>3^5 \equiv 1(\mod 121)</math> and <math>3^3 \equiv 1(\mod 13)</math>. Now we must find the smallest <math>k</math> such that <math>3^{3k} \equiv 1(\mod 13)</math>. Euler's gives <math>3^{156} \equiv 1(\mod 169)</math>. So <math>3k</math> is a factor of <math>156</math>. This gives <math>k=1,2, 4, 13, 26, 52</math>. Some more inspection yields <math>k=13</math> is the smallest valid <math>k</math>. So <math>3^5 \equiv 1(\mod 121)</math> and <math>3^{39} \equiv 1(\mod 169)</math>. The least <math>n</math> satisfying both is <math>lcm[5,39]=\boxed{195}</math>. (RegularHexagon) |
==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 10:59, 8 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
Solution
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)
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.