Difference between revisions of "2020 AIME I Problems/Problem 12"
Fireflame241 (talk | contribs) (→Solution 2 (Simpler, just basic mods and Fermat's theorem)) |
Fireflame241 (talk | contribs) (→Solution 1) |
||
Line 5: | Line 5: | ||
Lifting the Exponent shows that <cmath>v_3(149^n-2^n) = v_3(n) + v_3(147) = v_3(n)+1</cmath> so thus, <math>3^2</math> divides <math>n</math>. It also shows that <cmath>v_7(149^n-2^n) = v_7(n) + v_7(147) = v_7(n)+2</cmath> so thus, <math>7^5</math> divides <math>n</math>. | Lifting the Exponent shows that <cmath>v_3(149^n-2^n) = v_3(n) + v_3(147) = v_3(n)+1</cmath> so thus, <math>3^2</math> divides <math>n</math>. It also shows that <cmath>v_7(149^n-2^n) = v_7(n) + v_7(147) = v_7(n)+2</cmath> so thus, <math>7^5</math> divides <math>n</math>. | ||
+ | The divisibility criterion implies <math>149^n\equiv 2^n \pmod{5}</math>. This only occurs when <math>4 | n</math>, so let <math>n=4m</math>. We see <cmath>5 = v_5(149^{4m}-2^{4m}) = v_5((149^4)^{m}-(2^4)^{m}) = v_5(149^4-2^4)+v_5(m)</cmath> Since <math>149^{4} \equiv 1 \pmod{25}</math> and <math>16^1 \equiv 16 \pmod{25}</math>, then <math>v_5(149^4-2^4)=1</math>, so <math>v_5(m)=5</math>, hence <math>4 \cdot 5^4</math> divides <math>n</math>. | ||
− | + | Since <math>3^2</math>, <math>7^5</math> and <math>4\cdot 5^4</math> all divide <math>n</math>, the smallest value of <math>n</math> working is their LCM, also <math>3^2 \cdot 7^5 \cdot 4 \cdot 5^4 = 2^2 \cdot 3^2 \cdot 5^4 \cdot 7^5</math>. Thus the number of divisors is <math>(2+1)(2+1)(4+1)(5+1) = \boxed{270}</math>. | |
− | + | ~kevinmathz + fireflame241 | |
− | |||
== Solution 2 (Simpler, just basic mods and Fermat's theorem)== | == Solution 2 (Simpler, just basic mods and Fermat's theorem)== | ||
Revision as of 21:52, 13 March 2020
Contents
Problem
Let be the least positive integer for which is divisible by Find the number of positive integer divisors of
Solution 1
Lifting the Exponent shows that so thus, divides . It also shows that so thus, divides .
The divisibility criterion implies . This only occurs when , so let . We see Since and , then , so , hence divides .
Since , and all divide , the smallest value of working is their LCM, also . Thus the number of divisors is .
~kevinmathz + fireflame241
Solution 2 (Simpler, just basic mods and Fermat's theorem)
Note that for all n, is divisible by 1 because that is a factor. That is , so now we can clearly see that the smallest to make the expression divisible by is just . Similarly, we can reason that the smallest n to make the expression divisible by is just .
Finally, for , take mod and mod of each quantity (They happen to both be and respectively, so you only need to compute once). One knows from Fermat's theorem that the maximum possible minimum for divisibility by is , and other values are factors of . Testing all of them (just using mods-not too bad), is indeed the smallest value to make the expression divisible by , and this clearly is NOT divisible by . Therefore, the smallest to make this expression divisible by is .
Calculating the LCM of all these, one gets . Using the factor counting formula, the answer is = .
-Solution by thanosaops
See Also
2020 AIME I (Problems • Answer Key • Resources) | ||
Preceded by Problem 11 |
Followed by Problem 13 | |
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.