Prove that there is no positive integer s.t. $1000^m-1$ divides $1396^m-1$

Prove that there is no positive integer s.t. $1000^m-1$ divides $1396^m-1$.

I was looking for a divisor of $1000^m-1$ such that it is not a divisor of $1396^m-1$. Like $1000^m-1 \equiv 0 \pmod{37}$, but I couldn't prove that $1396^m-1 \equiv 27^m-1 \not\equiv 0 \pmod{37}$. Please help me solve this

• I'm not exactly sure how to solve this problem, but I do know that there exists a positive integer $m$ such that $999|(1396^m-1)$, so your approach won't work. – Carl Schildkraut Jul 6 '17 at 16:16
• You are right. My approach will not help. – M. Chun Jul 6 '17 at 16:18
• @CarlSchildkraut the exponent must be the same – Raffaele Jul 6 '17 at 16:18
• @Raffaele I know. I'm just saying that there's no number that always divides $1000^m-1$ (for all $m$) that never divides $1396^m-1$. – Carl Schildkraut Jul 6 '17 at 17:45

Using Lifting The Exponent, we get $$v_3(1000^m-1) = v_3(1000-1)+v_3(m) = 3+v_3(m)$$ while $$v_3(1396^m-1) = v_3(1396-1)+v_3(m) = 2+v_3(m).$$ So since $3+v_3(m) > 2+v_3(m)$, $1000^m-1 \nmid 1396^m-1$.