Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

Thanks.

share|improve this question
    
What do we know about the converse ?! –  kian Mar 31 at 8:55

5 Answers 5

up vote 14 down vote accepted

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

share|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|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|improve this answer
    
How about the converse ? –  kian Mar 31 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|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|improve this answer

Your Answer

 
discard

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.