Difference between revisions of "2020 AIME I Problems/Problem 12"
(→Solution 3 (Elementary and Thorough)) |
m (→Solution 3 (Elementary and Thorough)) |
||
Line 28: | Line 28: | ||
== Solution 3 (Elementary and Thorough) == | == Solution 3 (Elementary and Thorough) == | ||
− | As usual, denote <math>v_p(n)</math> the highest power of prime <math>p</math> that divides <math>n</math>. For divisibility by <math>3^3</math>, notice that <math>v_3(149^3 - 2^3) = 2</math> as <math>149^3 - 2^3 =</math> <math>(147)(149^2 + 2\cdot149 + 2^2)</math>, and upon checking mods, <math>149^2 + 2\cdot149 + 2^2</math> is divisible by <math>3</math> but not <math>9</math>. In addition, <math>149^9 - 3^9</math> is divisible by <math>3^3</math> because <math>149^9 - 3^9 = (149^3 - 3^3)(149^6 + 149^3\cdot2^3 + 2^6)</math>, and the rightmost factor equates to <math>1 + 1 + 1 \pmod{3} \equiv 0 \pmod{3}</math>. In fact, <math>n = 9 = 3^2</math> is the least possible choice to ensure divisibility by <math>3^3</math> because if <math>n = a \cdot 3^b</math>, with <math>3 \nmid a</math> and <math>b < 2</math>, we write <cmath>149^{a \cdot 3^b} - 2^{a \cdot 3^b} = (149^{3^b} - 2^{3^b})(149^{3^b(a - 1)} + 149^{3^b(a - 2)}\cdot2^{3^b}+\cdots2^{3^b(a - 1)}).</cmath> Then, the rightmost factor is equivalent to <math> | + | As usual, denote <math>v_p(n)</math> the highest power of prime <math>p</math> that divides <math>n</math>. For divisibility by <math>3^3</math>, notice that <math>v_3(149^3 - 2^3) = 2</math> as <math>149^3 - 2^3 =</math> <math>(147)(149^2 + 2\cdot149 + 2^2)</math>, and upon checking mods, <math>149^2 + 2\cdot149 + 2^2</math> is divisible by <math>3</math> but not <math>9</math>. In addition, <math>149^9 - 3^9</math> is divisible by <math>3^3</math> because <math>149^9 - 3^9 = (149^3 - 3^3)(149^6 + 149^3\cdot2^3 + 2^6)</math>, and the rightmost factor equates to <math>1 + 1 + 1 \pmod{3} \equiv 0 \pmod{3}</math>. In fact, <math>n = 9 = 3^2</math> is the least possible choice to ensure divisibility by <math>3^3</math> because if <math>n = a \cdot 3^b</math>, with <math>3 \nmid a</math> and <math>b < 2</math>, we write <cmath>149^{a \cdot 3^b} - 2^{a \cdot 3^b} = (149^{3^b} - 2^{3^b})(149^{3^b(a - 1)} + 149^{3^b(a - 2)}\cdot2^{3^b}+\cdots2^{3^b(a - 1)}).</cmath> Then, the rightmost factor is equivalent to <math>pma \pmod{3} \not\equiv 0 \pmod{3}</math>, and <math>v_3(149^{3^b} - 2^{3^b}) = b + 1 < 3</math>. |
For divisibility by <math>7^7</math>, we'll induct, claiming that <math>v_7(149^{7^k} - 2^{7^k}) = k + 2</math> for whole numbers <math>k</math>. The base case is clear. Then, <cmath>v_7(149^{7^{k+1}} - 2^{7^{k+1}}) = v_7(149^{7^k} - 2^{7^k}) + v_7(149^{6\cdot7^k} + 2^{7^k}\cdot149^{5\cdot7^k} + \cdots + 2^{5\cdot7^k}\cdot149^{7^k} + 2^{6\cdot7^k}).</cmath> By the induction hypothesis, <math>v_7(149^{7^k} - 2^{7^k}) = k + 2</math>. Then, notice that <cmath>S(k) = 149^{6\cdot7^k} + 2^{7^k}\cdot149^{5\cdot7^k} + \cdots + 2^{5\cdot7^k}\cdot149^{7^k} + 2^{6\cdot7^k} \equiv 7 \cdot 2^{6\cdot7^k}\pmod{7} \equiv 7 \cdot 2^{6\cdot7^k}\pmod{49}.</cmath> This tells us that <math>S(k)</math> is divisible by <math>7</math>, but not <math>49</math> so that <math>v_7\left(S(k)\right) = 1</math>, completing our induction. We can verify that <math>7^5</math> is the least choice of <math>n</math> to ensure divisibility by <math>7^7</math> by arguing similarly to the <math>3^3</math> case. | For divisibility by <math>7^7</math>, we'll induct, claiming that <math>v_7(149^{7^k} - 2^{7^k}) = k + 2</math> for whole numbers <math>k</math>. The base case is clear. Then, <cmath>v_7(149^{7^{k+1}} - 2^{7^{k+1}}) = v_7(149^{7^k} - 2^{7^k}) + v_7(149^{6\cdot7^k} + 2^{7^k}\cdot149^{5\cdot7^k} + \cdots + 2^{5\cdot7^k}\cdot149^{7^k} + 2^{6\cdot7^k}).</cmath> By the induction hypothesis, <math>v_7(149^{7^k} - 2^{7^k}) = k + 2</math>. Then, notice that <cmath>S(k) = 149^{6\cdot7^k} + 2^{7^k}\cdot149^{5\cdot7^k} + \cdots + 2^{5\cdot7^k}\cdot149^{7^k} + 2^{6\cdot7^k} \equiv 7 \cdot 2^{6\cdot7^k}\pmod{7} \equiv 7 \cdot 2^{6\cdot7^k}\pmod{49}.</cmath> This tells us that <math>S(k)</math> is divisible by <math>7</math>, but not <math>49</math> so that <math>v_7\left(S(k)\right) = 1</math>, completing our induction. We can verify that <math>7^5</math> is the least choice of <math>n</math> to ensure divisibility by <math>7^7</math> by arguing similarly to the <math>3^3</math> case. |
Revision as of 00:27, 23 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 .
Now, multiplying by , we see and since and then meaning that we have that by LTE, divides .
Since , and all divide , the smallest value of working is their LCM, also . Thus the number of divisors is .
~kevinmathz
Solution 2 (Simpler, just basic mods and Fermat's theorem)
BY THE WAY, please feel free to correct my formatting. I don't know latex.
Note that for all , is divisible by 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 to make the expression divisible by is just .
Finally, for , take and 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 = . Can someone please format better for me?
-Solution by thanosaops -formatted by MY-2
Solution 3 (Elementary and Thorough)
As usual, denote the highest power of prime that divides . For divisibility by , notice that as , and upon checking mods, is divisible by but not . In addition, is divisible by because , and the rightmost factor equates to . In fact, is the least possible choice to ensure divisibility by because if , with and , we write Then, the rightmost factor is equivalent to , and .
For divisibility by , we'll induct, claiming that for whole numbers . The base case is clear. Then, By the induction hypothesis, . Then, notice that This tells us that is divisible by , but not so that , completing our induction. We can verify that is the least choice of to ensure divisibility by by arguing similarly to the case.
Finally, for , we take the powers of and in mod and mod . Writing out these mods, we have that if and only if , in which . So here we claim that and perform yet another induction. The base case is true: , but . Now then, assuming the induction statement to hold for some , Note that equates to in both mod and mod . We notice that . Writing out the powers of mod , we have . Also when is a multiple of . Hence for , . Thus, , completing our induction. Applying the same argument from the previous two cases, is the least choice to ensure divisibility by .
Our answer is the number of divisors of . It is .
~hnkevin42
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.