Given that $149^n-2^n$ is divisible by $3^3\cdot5^5\cdot7^7$, find the number of positive integer divisors of $n$.

Question

I suddenly recalled one hard question (to me) in a math contest I participated in before. Fortunately I still completely remembered its context as follows:

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$.

I'm $100\%$ sure that I didn't manage to solve this back then, and right now I have already tried for half an hour but the triumph over this beast is still too far away from me.

What I know (really few) :

$149^n-2^n$ is apparently divisible by $147$, which is $3\cdot7^2$.

Therefore $n$ should be divisible by $3^2$ and $7^5$...... is that correct?

My Problem :

Unfortunately I don't know how to tackle the $5$ part. Maybe it has something to do with Fermat's theorem? Or am I missing out something important?

Any suggestions or hints will be much appreciated. Thanks. I am sorry if this is a bad post since I am not able to provide enough work of mine.

Answer 1

This follows immediately by standard facts about prime powers dividing binomials. If $\,p\,$ is prime then $\,v_p(n)\,$ is the power of $\,p\,$ in $n,\,$ i.e. $v_p(n) = k\iff p^k\,||\, n,\,$ i.e. $\,p^k\mid n,\ p^{k+1}\nmid n.\,$
The following is a standard theorem (widely known in the contest community).

Lifting The Exponent ($\,\rm\color{#c00}LTE$) $\ $ If $\,a,b,n\in\Bbb Z,\,$ $\,k\ge 1,\,$ odd prime $\,p\mid a\!-\!b,\,$ $\,p\nmid a,b\,$ then

$$\bbox[8px,border:1px solid #c00]{v_p(a^k\!-b^k)\, \overset{\rm\color{#c00}L}=\, v_p(a\!-\!b) + v_p(k)}\qquad\qquad\qquad\qquad\qquad$$

By hypothesis $\,3^3,5^5,7^7\!\mid I := a^n-2^n,\, a\!=\!149.\,$ Note $\,3,7^2\,||\, a\!-\!2,\,$ so applying LTE:

therefore $\ 3^3\!\mid\! I\!\iff 3\le v_3(I) \overset{\rm\color{#c00}L}= v_3(a\!-\!2) + v_3(n) = 1 + v_3(n)\!\iff \color{#c00}{v_3(n)\ge 2}$

Similarly $\:\!\ 7^7\!\mid\! I\!\iff 7\le v_7(I) \overset{\rm\color{#c00}L}= v_7(a\!-\!2) + v_7(n) = 2 + v_7(n)\iff \color{#90f}{v_7(n)\ge 5}$

Unlike above $\,5\nmid a\!-\!2\,$ so to apply LTE we seek the least $\,n\,$ with $\,5\mid I = a^n-2^n$.

$\!\!\bmod 5\!:\ 2^n\equiv a^n\equiv 4^n\!\iff 1\equiv 2^n\iff \color{#0a0}{4\mid n},\ $ say $\,n = 4j.\,$ Now LTE applies

$5^5\!\mid\! I\!\!\iff\!\! 5\!\le\! v_5(I) = v_5((a^{4})^j\!-\!(2^4)^j)\overset{\rm\color{#c00}L}= v_5(a^4\!-\!2^4)\!+\!v_5(j) = 1\!+\!v_5(j)\!\!\iff\!\! \color{#0a0}{v_5(j)\!\ge\! 4}$

Therefore $\,3^3 5^5 7^7\!\mid\! I\!\iff\! 3^3, 5^5, 7^7\!\mid\! I \!\iff\! \color{#c00}{3^2}, \color{#0a0}{4\cdot 5^4},\color{#90f}{ 7^5}\mid n \iff 3^2\cdot 4\cdot 5^4\cdot 7^5\mid n\ $ because LCM = product for pair coprimes.

Answer 2

For the least $n$ as in OP, use Euler's theorem. For example in the case of $5$, you have $\phi(5^5)=4\cdot 5^4$. Then look at $149^1,149^2,...$ mod $5^5$, and also at $2^1, 2^2,...$ mod $5^5$. These are periodic sequences, so you need to find the lengths and the first common number in the two sequences.

Same for $3^3$ and $7^7$.

You can also use Hensel's lemma but I am not sure it is allowed. A slightly easier approach is to find the inverse $s$ of $2$ modulo, say, $5^5$ and instead of $149^n-2^n$ consider $(149s)^n-1$.

Addition The last approach is what Robert Israel is doing in his answer. So it is not that easy.

Answer 3

I don't know how you'd do all this by hand in a math contest, but here's a solution with some computer help.

$149 \cdot 2^{-1} \equiv 7 \mod 3^3$, and this has order $9$ mod $3^3$.

$149 \cdot 2^{-1} \equiv 1637 \mod 5^5$, and this has order $2500$ mod $5^5$.

$149 \cdot 2^{-1} \equiv 411846 \mod 7^7$, and this has order $16807$ mod $7^7$.

So the least possible $n$ is $\text{lcm}(9,2500,16807) = 378157500$.