Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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 \exists k \in \mathbb{N} $ such that $bk=a$ and then raising $n$ to the power of the LHS and the RHS 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?


share|cite|improve this question
What do we know about the converse ?! – kian Mar 31 '14 at 8:55
up vote 14 down vote accepted

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

share|cite|improve this answer
...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).

share|cite|improve this answer

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

share|cite|improve this answer
How about the converse ? – kian Mar 31 '14 at 8:56

There is a very useful identity $$ x^n-y^n=(x-y)(x^{n-1}+x^{n-2}y+\cdots+y^{n-1}). $$ Substituting $y$ with 1 here, we get $$ n^a-1=(n-1)(n^{a-1}+n^{a-2}+\cdots+1). $$ Now since $b|a$, there exists some $k\in\mathbb{Z}$ such that $a=bk$. Therefore, $$ n^a-1={(n^b)}^k-1=(n^b-1)((n^b)^{k-1}+(n^b)^{k-2}+\cdots+1). $$ Hence, $(n^b-1)|(n^a-1)$.

share|cite|improve this answer

Let $a=bk$ with $k \in \mathbb{N}$. We have $n^a-1=n^{bk}-1= (n^b-1) \left( n^{b(k-1)}+n^{b(k-2)}+ \cdots + n^b+1 \right)$. Thus $n^b-1|n^a-1$.

REMARK. This problem is very useful. For example: Find all positive integer numbers $n$ such that $n^2|2^n+1$.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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