Let $n > 1$ and $m$ and $r$ be positive integers. Prove that $(n^r −1)$ divides $(n^m −1)$ if and only if $r$ divides $m$.


If $r\mid m$, then let $m=rk$. Then $$n^r-1\mid n^{rk}-1=\left(n^r-1\right)\left(n^{rk-r}+n^{rk-r-1}+\cdots+1\right)$$

If $n^{r}-1\mid n^m-1$, then $\text{ord}_{n^r-1}(n)=r$, so by the below Lemma $r\mid m$.

Lemma: If $x^t\equiv 1\pmod{m}$, then $\text{ord}_m(x)\mid t$.

Proof: For contradiction, let $t=\text{ord}_m(x)h+r$ for some $0<r<\text{ord}_m(x)$. But then:

$$1\equiv x^t\equiv \left(x^{\text{ord}_m(x)}\right)^hx^r\equiv 1^hx^r\equiv x^r\pmod{m},$$



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