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

  • $\begingroup$ 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. $\endgroup$ – Carl Schildkraut Jul 6 '17 at 16:16
  • $\begingroup$ You are right. My approach will not help. $\endgroup$ – M. Chun Jul 6 '17 at 16:18
  • $\begingroup$ @CarlSchildkraut the exponent must be the same $\endgroup$ – Raffaele Jul 6 '17 at 16:18
  • $\begingroup$ @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$. $\endgroup$ – 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$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.