Difference between revisions of "2020 AIME I Problems/Problem 12"

(Solution)
m (Clarified the meaning of part of the solution)
(30 intermediate revisions by 13 users not shown)
Line 1: Line 1:
Note: Please do not post problems here until after the AIME.
 
 
 
== Problem ==
 
== Problem ==
 
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 ==
+
== 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>.  
 
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>.  
  
Now, multiplying <math>n</math> by <math>4</math>, we see <cmath>v_5(149^{4n}-2^{4n}) = v_5(149^{4n}-16^{n})</cmath> and since <math>145^{4} \equiv 1 \pmod{25}</math> and <math>16^1 \equiv 16 \pmod{25}</math> then <math>v_5(149^{4n}-2^{4n})=1</math> meaning that we have that by LTE, <math>4 \cdot 5^4</math> divides <math>n</math>.  
+
 
 +
Now, multiplying <math>n</math> by <math>4</math>, we see <cmath>v_5(149^{4n}-2^{4n}) = v_5(149^{4n}-16^{n})</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^{4n}-2^{4n})=1+v_5(n)</math> meaning that we have that by LTE, <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
 +
 +
 +
Lol you can get <math>4 \cdot 5^4</math> by just Euler Totient.
 +
 +
~LLL2019
 +
 +
== 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
 +
 +
~formatted by MY-2
 +
 +
~also formatted by 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
  
 
==See Also==
 
==See Also==

Revision as of 15:18, 6 November 2020

Problem

Let $n$ be the least positive integer for which $149^n-2^n$ is divisible by $3^3\cdot5^5\cdot7^7.$ Find the number of positive integer divisors of $n.$

Solution 1

Lifting the Exponent shows that \[v_3(149^n-2^n) = v_3(n) + v_3(147) = v_3(n)+1\] so thus, $3^2$ divides $n$. It also shows that \[v_7(149^n-2^n) = v_7(n) + v_7(147) = v_7(n)+2\] so thus, $7^5$ divides $n$.


Now, multiplying $n$ by $4$, we see \[v_5(149^{4n}-2^{4n}) = v_5(149^{4n}-16^{n})\] and since $149^{4} \equiv 1 \pmod{25}$ and $16^1 \equiv 16 \pmod{25}$ then $v_5(149^{4n}-2^{4n})=1+v_5(n)$ meaning that we have that by LTE, $4 \cdot 5^4$ divides $n$.

Since $3^2$, $7^5$ and $4\cdot 5^4$ all divide $n$, the smallest value of $n$ working is their LCM, also $3^2 \cdot 7^5 \cdot 4 \cdot 5^4 = 2^2 \cdot 3^2 \cdot 5^4 \cdot 7^5$. Thus the number of divisors is $(2+1)(2+1)(4+1)(5+1) = \boxed{270}$.

~kevinmathz


Lol you can get $4 \cdot 5^4$ by just Euler Totient.

~LLL2019

Solution 2 (Simpler, just basic mods and Fermat's theorem)

Note that for all $n$, $149^n - 2^n$ is divisible by $149-2 = 147$ by difference of $n$th powers. That is $3\cdot7^2$, so now we can clearly see that the smallest $n$ to make the expression divisible by $3^3$ is just $3^2$. Similarly, we can reason that the smallest $n$ to make the expression divisible by $7^7$ is just $7^5$.

Finally, for $5^5$, take $\pmod {5}$ and $\pmod {25}$ of each quantity (They happen to both be $-1$ and $2$ respectively, so you only need to compute once). One knows from Fermat's theorem that the maximum possible minimum $n$ for divisibility by $5$ is $4$, and other values are factors of $4$. Testing all of them(just $1$,$2$,$4$ using mods-not too bad), $4$ is indeed the smallest value to make the expression divisible by $5$, and this clearly is NOT divisible by $25$. Therefore, the smallest $n$ to make this expression divisible by $5^5$ is $2^2 \cdot 5^4$.

Calculating the LCM of all these, one gets $2^2 \cdot 3^2 \cdot 5^4 \cdot 7^5$. Using the factor counting formula, the answer is $3\cdot3\cdot5\cdot6$ = $\boxed{270}$.

~Solution by thanosaops

~formatted by MY-2

~also formatted by pandyhu2001

Solution 3 (Elementary and Thorough)

As usual, denote $v_p(n)$ the highest power of prime $p$ that divides $n$. For divisibility by $3^3$, notice that $v_3(149^3 - 2^3) = 2$ as $149^3 - 2^3 =$ $(147)(149^2 + 2\cdot149 + 2^2)$, and upon checking mods, $149^2 + 2\cdot149 + 2^2$ is divisible by $3$ but not $9$. In addition, $149^9 - 2^9$ is divisible by $3^3$ because $149^9 - 2^9 = (149^3 - 2^3)(149^6 + 149^3\cdot2^3 + 2^6)$, and the rightmost factor equates to $1 + 1 + 1 \pmod{3} \equiv 0 \pmod{3}$. In fact, $n = 9 = 3^2$ is the least possible choice to ensure divisibility by $3^3$ because if $n = a \cdot 3^b$, with $3 \nmid a$ and $b < 2$, we write \[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)}).\] Then, the rightmost factor is equivalent to $\pm a \pmod{3} \not\equiv 0 \pmod{3}$, and $v_3(149^{3^b} - 2^{3^b}) = b + 1 < 3$.

For divisibility by $7^7$, we'll induct, claiming that $v_7(149^{7^k} - 2^{7^k}) = k + 2$ for whole numbers $k$. The base case is clear. Then, \[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}).\] By the induction hypothesis, $v_7(149^{7^k} - 2^{7^k}) = k + 2$. Then, notice that \[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}.\] This tells us that $S(k)$ is divisible by $7$, but not $49$ so that $v_7\left(S(k)\right) = 1$, completing our induction. We can verify that $7^5$ is the least choice of $n$ to ensure divisibility by $7^7$ by arguing similarly to the $3^3$ case.

Finally, for $5^5$, we take the powers of $149$ and $2$ in mod $5$ and mod $25$. Writing out these mods, we have that $149^n \equiv 2^n \pmod{5}$ if and only if $4 | n$, in which $149^n \equiv 2^n \equiv 1 \pmod{5}$. So here we claim that $v_5(149^{4\cdot5^k} - 2^{4\cdot5^k}) = k + 1$ and perform yet another induction. The base case is true: $5 | 149^4 - 2^4$, but $149^4 - 2^4 \equiv 1 - 16 \pmod{25}$. Now then, assuming the induction statement to hold for some $k$, \[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}).\] Note that $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}$ equates to $S''(k) = 1 + 2^{4\cdot5^k} + \cdots + 2^{16\cdot5^k}$ in both mod $5$ and mod $25$. We notice that $S''(k) \equiv 0 \pmod{5}$. Writing out the powers of $2$ mod $25$, we have $S''(0) \equiv 5 \pmod{25}$. Also $2^n \equiv 1 \pmod{25}$ when $n$ is a multiple of $20$. Hence for $k > 0$, $S''(k) \equiv 5 \mod{25}$. Thus, $v_5\left(S'(k)\right) = 1$, completing our induction. Applying the same argument from the previous two cases, $4\cdot5^4$ is the least choice to ensure divisibility by $5^5$.

Our answer is the number of divisors of $\text{lcm}(3^2, 7^5, 2^2\cdot5^4) = 2^2 \cdot 3^2 \cdot 5^4 \cdot 7^5$. It is $(2 + 1)(2 + 1)(4 + 1)(5 + 1) = \boxed{270}$.

~hnkevin42

See Also

2020 AIME I (ProblemsAnswer KeyResources)
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. AMC logo.png