# Prove that $b\mid a \implies (n^b-1)\mid (n^a-1)$

Given natural numbers $a,b,n$, prove $b\mid a \implies (n^b-1)\mid (n^a-1)$.

I tried the simple method of beginning with $b\mid a \implies$ there exists a natural $k$ such that $bk=a$ and then raising $n$ to the power of the LHS and the RHS side and eventually forming $(n^b)^k-1=n^a-1$. That's obviously not enough. It tried making it work from the other side and didn't get too far either. I guess there's some $gcd$ theorem or something I need.

Any ideas?

Thanks.

-

$(n^b-1) (1 + n^b + n^{2b} + \dots + n^{(k-1)b}) = n^a - 1$

-
 ...or maybe just some good old brute force. Apparently, it's simpler than I thought it'd be. Thanks! – shwartz Mar 22 '11 at 8:38

At the heart, it's the trivial identity $\rm\ 1^m \equiv 1.\$ Since $\rm\ b\:|\:a\$ we have $\rm\ a = b\ m\:,\$ for some $\rm\ m\in \mathbb Z.$

Therefore $\rm \ mod\,\ n^b-1\!:\,\ n^b \equiv 1\ \Rightarrow\ n^a \equiv (n^b)^m\equiv 1^m \equiv 1,\$ hence $\rm\ n^b-1\ |\ n^a - 1\:.$

Alternatively put $\rm\ x = n^b\$ in $\rm\ x-1\ |\ x^m - 1,\:$ by the Factor Theorem $\rm\ x-a\ |\ f(x)-f(a)\$ in $\rm\ \mathbb Z[x]\:.$

See this question for the special case $\rm\ x+1\ |\ x^m+1\$ for $\rm\:m\:$ odd (follows by $\rm\ x\to -x\$ above).

-

I write the thing in terms of Cyclotomic polynomials:

$$n^k - 1 = \prod_{d|k} \Phi_d(n).$$

Now it is proved because the divisors of $b$ are a subset of the divisors of $a$ so the cyclotomic factors of $n^b - 1$ are a subset of the cyclotomic factors of $n^a - 1$.

-