Difference between revisions of "2020 AIME I Problems/Problem 12"
Thanosaops (talk | contribs) (→Solution 2 (For people who don't know like crazy stuff)) |
Mathboy282 (talk | contribs) (→Solution 1) |
||
(36 intermediate revisions by 21 users not shown) | |||
Line 2: | Line 2: | ||
Let <math>n</math> be the least positive integer for which <math>149^n-2^n</math> is divisible by <math>3^3\cdot5^5\cdot7^7.</math> Find the number of positive integer divisors of <math>n.</math> | Let <math>n</math> be the least positive integer for which <math>149^n-2^n</math> is divisible by <math>3^3\cdot5^5\cdot7^7.</math> Find the number of positive integer divisors of <math>n.</math> | ||
− | == Solution 1== | + | ==Solution 1== |
− | 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>. | + | As usual, denote <math>v_p(n)</math> the highest power of prime <math>p</math> that divides <math>n</math>. |
+ | [[Lifting the Exponent]] shows that <cmath>3=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>7=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>. | ||
− | Now, | + | Now, setting <math>n = 4c</math> (necessitated by <math>149^n \equiv 2^n \pmod 5</math> in order to set up LTE), we see <cmath>v_5(149^{4c}-2^{4c}) = v_5(149^{4c}-16^{c})</cmath> and since <math>149^{4} \equiv 1 \pmod{25}</math> and <math>16^1 \equiv 16 \pmod{25}</math> then <math>v_5(149^{4c}-2^{4c})=v_5(149^4-16)+v_5(c)=1+v_5(c)</math> meaning that we have that by LTE, <math>5^4 | c</math> and <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>. | 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 | ~kevinmathz | ||
+ | |||
+ | clarified by another user | ||
+ | |||
+ | notation note from another user | ||
+ | |||
+ | ===Note=== | ||
+ | We were able to use LTE with 3 and 7 but not 5 because in order to use LTE, we need | ||
+ | |||
+ | Obviously, | ||
+ | |||
+ | Furthermore, | ||
+ | |||
+ | However, when we get to the case of 5, we see that | ||
+ | |||
+ | '''mathboy282''' | ||
+ | |||
== Solution 2 (Simpler, just basic mods and Fermat's theorem)== | == Solution 2 (Simpler, just basic mods and Fermat's theorem)== | ||
− | + | Note that for all <math>n</math>, <math>149^n - 2^n</math> is divisible by <math>149-2 = 147</math> by difference of <math>n</math>th powers. That is <math>3\cdot7^2</math>, so now we can clearly see that the smallest <math>n</math> to make the expression divisible by <math>3^3</math> is just <math>3^2</math>. Similarly, we can reason that the smallest <math>n</math> to make the expression divisible by <math>7^7</math> is just <math>7^5</math>. | |
− | + | Finally, for <math>5^5</math>, take <math>\pmod {5}</math> and <math>\pmod {25}</math> of each quantity (They happen to both be <math>-1</math> and <math>2</math> respectively, so you only need to compute once). One knows from [[Fermat's theorem]] that the maximum possible minimum <math>n</math> for divisibility by <math>5</math> is <math>4</math>, and other values are factors of <math>4</math>. Testing all of them(just <math>1</math>,<math>2</math>,<math>4</math> using mods-not too bad), <math>4</math> is indeed the smallest value to make the expression divisible by <math>5</math>, and this clearly is NOT divisible by <math>25</math>. | |
+ | Therefore, the smallest <math>n</math> to make this expression divisible by <math>5^5</math> is <math>2^2 \cdot 5^4</math>. | ||
− | + | Calculating the LCM of all these, one gets <math>2^2 \cdot 3^2 \cdot 5^4 \cdot 7^5</math>. Using the factor counting formula, | |
− | + | the answer is <math>3\cdot3\cdot5\cdot6</math> = <math>\boxed{270}</math>. | |
− | + | ~Solution by thanosaops | |
− | |||
− | |||
− | -Solution by | + | ~formatted by MY-2 and pandyhu2001 |
+ | |||
+ | == 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 - 2^9</math> is divisible by <math>3^3</math> because <math>149^9 - 2^9 = (149^3 - 2^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>\pm a \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. | ||
+ | |||
+ | Finally, for <math>5^5</math>, we take the powers of <math>149</math> and <math>2</math> in mod <math>5</math> and mod <math>25</math>. Writing out these mods, we have that <math>149^n \equiv 2^n \pmod{5}</math> if and only if <math>4 | n</math>, in which <math>149^n \equiv 2^n \equiv 1 \pmod{5}</math>. So here we claim that <math>v_5(149^{4\cdot5^k} - 2^{4\cdot5^k}) = k + 1</math> and perform yet another induction. The base case is true: <math>5 | 149^4 - 2^4</math>, but <math>149^4 - 2^4 \equiv 1 - 16 \pmod{25}</math>. Now then, assuming the induction statement to hold for some <math>k</math>, <cmath>v_5(149^{4\cdot5^{k+1}} - 2^{4\cdot5^{k+1}}) = (k+1) + v_5(149^{4\cdot4\cdot5^k}+2^{4\cdot5^k}\cdot149^{3\cdot4\cdot5^k}+\cdots+2^{3\cdot4\cdot5^k}\cdot149^{4\cdot5^k}+2^{4\cdot4\cdot5^k}).</cmath> Note that <math>S'(k) = 149^{4\cdot4\cdot5^k}+2^{4\cdot5^k}\cdot149^{3\cdot4\cdot5^k}+\cdots+2^{3\cdot4\cdot5^k}\cdot149^{4\cdot5^k}+2^{4\cdot4\cdot5^k}</math> equates to <math>S''(k) = 1 + 2^{4\cdot5^k} + \cdots + 2^{16\cdot5^k}</math> in both mod <math>5</math> and mod <math>25</math>. We notice that <math>S''(k) \equiv 0 \pmod{5}</math>. Writing out the powers of <math>2</math> mod <math>25</math>, we have <math>S''(0) \equiv 5 \pmod{25}</math>. Also <math>2^n \equiv 1 \pmod{25}</math> when <math>n</math> is a multiple of <math>20</math>. Hence for <math>k > 0</math>, <math>S''(k) \equiv 5 \mod{25}</math>. Thus, <math>v_5\left(S'(k)\right) = 1</math>, completing our induction. Applying the same argument from the previous two cases, <math>4\cdot5^4</math> is the least choice to ensure divisibility by <math>5^5</math>. | ||
+ | |||
+ | Our answer is the number of divisors of <math>\text{lcm}(3^2, 7^5, 2^2\cdot5^4) = 2^2 \cdot 3^2 \cdot 5^4 \cdot 7^5</math>. It is <math>(2 + 1)(2 + 1)(4 + 1)(5 + 1) = \boxed{270}</math>. | ||
+ | |||
+ | ~hnkevin42 | ||
+ | |||
+ | ==Solution 4 (Official MAA)== | ||
+ | Analyze each prime power separately. | ||
+ | Start with the case of <math>3^3</math>. By the Binomial Theorem, | ||
+ | <cmath>\begin{align*} | ||
+ | 149^n - 2^n &= (147+2)^n - 2^n \ | ||
+ | &= \binom n1 \cdot 147 \cdot 2^{n-1} | ||
+ | + \binom n2 \cdot 147^2 \cdot 2^{n-2}\ | ||
+ | &\qquad+ \binom n3 \cdot 147^3 \cdot 2^{n-3} | ||
+ | + \cdots. | ||
+ | \end{align*}</cmath>Because <math>147</math> is divisible by <math>3</math>, all terms after the first two are divisible by <math>3^3</math>, and the exponent of <math>3</math> in the first term is less than that in the second term. Hence it is necessary and sufficient that <math>3^3 \mid 147n</math>, that is, <math>3^2 \mid n</math>. | ||
+ | For the <math>7^7</math> case, consider the same expansion as in the previous case. Because <math>147</math> is divisible by <math>49 = 7^2</math>, all terms after the first three are divisible by <math>7^7</math>, and the exponent of <math>7</math> in the first term is less than that in the second and third term. Hence it is necessary and sufficient that <math>7^7 \mid 147n</math>, that is, <math>7^5 \mid n</math>. | ||
+ | For the <math>5^5</math> case, working modulo <math>5</math> gives <math>149^n - 2^n \equiv 4^n - 2^n = 2^n(2^n-1) \pmod 5</math>, so it must be that <math>4 \mid n</math>. Let <math>n = 4m</math>, and let <math>c = 149^4 - 2^4 = (149^2-2^2)(149^2+2^2) = 147 \cdot 151 \cdot 22205</math>. Note that <math>\frac c5</math> is an integer not divisible by <math>5</math>. Expand by the Binomial Theorem again to get | ||
+ | <cmath>\begin{align*} | ||
+ | (149^4)^m - (2^4)^m &= (c+16)^m - (16)^m \ | ||
+ | &= \binom m1 \cdot c \cdot 16^{m-1} | ||
+ | + \binom m2 \cdot c^2 \cdot 16^{m-2} \ | ||
+ | &\qquad+ \binom m3 \cdot c^3 \cdot 16^{m-3} | ||
+ | + \binom m4 \cdot c^4 \cdot 16^{m-4} | ||
+ | + \cdots. | ||
+ | \end{align*}</cmath>All terms after the first four are divisible by <math>5^5</math>, and the exponent of <math>5</math> in the first term is less than that in the second, third, or fourth term. Hence it is necessary and sufficient that <math>5^5 \mid cm</math>. Thus <math>5^4 \mid m</math>, and it follows that <math>4 \cdot 5^4 \mid n</math>. | ||
+ | Therefore the least <math>n</math> is <math>3^2 \cdot (2^2 \cdot 5^4) \cdot 7^5</math>. The requested number of divisors is <math>(1+2)(1+2)(1+4)(1+5) = 270</math>. | ||
+ | |||
+ | The results of the above cases can be generalized using the following lemma. | ||
+ | |||
+ | Lifting the Exponent Lemma: Let <math>p</math> be an odd prime, and let <math>a</math> and <math>b</math> be integers relatively prime to <math>p</math> such that <math>p \mid (a-b)</math>. Let <math>n</math> be a positive integer. Then the number of factors of <math>p</math> that divide <math>a^n - b^n</math> is equal to the number of factors of <math>p</math> that divide <math>a-b</math> plus the number of factors of <math>p</math> that divide <math>n</math>. | ||
+ | |||
+ | == Video Solution == | ||
+ | https://www.youtube.com/watch?v=O0BprEOVkjo | ||
+ | ~ Math Gold Medalist | ||
==See Also== | ==See Also== | ||
Line 29: | Line 86: | ||
{{AIME box|year=2020|n=I|num-b=11|num-a=13}} | {{AIME box|year=2020|n=I|num-b=11|num-a=13}} | ||
{{MAA Notice}} | {{MAA Notice}} | ||
+ | |||
+ | [[Category: Intermediate Number Theory Problems]] |
Latest revision as of 02:50, 21 January 2024
Contents
[hide]Problem
Let be the least positive integer for which is divisible by Find the number of positive integer divisors of
Solution 1
As usual, denote the highest power of prime that divides . Lifting the Exponent shows that so thus, divides . It also shows that so thus, divides .
Now, setting (necessitated by in order to set up LTE), we see and since and then meaning that we have that by LTE, and divides .
Since , and all divide , the smallest value of working is their LCM, also . Thus the number of divisors is .
~kevinmathz
clarified by another user
notation note from another user
Note
We were able to use LTE with 3 and 7 but not 5 because in order to use LTE, we need
Obviously,
Furthermore,
However, when we get to the case of 5, we see that
mathboy282
Solution 2 (Simpler, just basic mods and Fermat's theorem)
Note that for all , is divisible by by difference of th powers. 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 = .
~Solution by thanosaops
~formatted by MY-2 and pandyhu2001
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
Solution 4 (Official MAA)
Analyze each prime power separately. Start with the case of . By the Binomial Theorem, Because is divisible by , all terms after the first two are divisible by , and the exponent of in the first term is less than that in the second term. Hence it is necessary and sufficient that , that is, . For the case, consider the same expansion as in the previous case. Because is divisible by , all terms after the first three are divisible by , and the exponent of in the first term is less than that in the second and third term. Hence it is necessary and sufficient that , that is, . For the case, working modulo gives , so it must be that . Let , and let . Note that is an integer not divisible by . Expand by the Binomial Theorem again to get All terms after the first four are divisible by , and the exponent of in the first term is less than that in the second, third, or fourth term. Hence it is necessary and sufficient that . Thus , and it follows that . Therefore the least is . The requested number of divisors is .
The results of the above cases can be generalized using the following lemma.
Lifting the Exponent Lemma: Let be an odd prime, and let and be integers relatively prime to such that . Let be a positive integer. Then the number of factors of that divide is equal to the number of factors of that divide plus the number of factors of that divide .
Video Solution
https://www.youtube.com/watch?v=O0BprEOVkjo ~ Math Gold Medalist
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.