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

From "Fundamentals of Number Theory" by William J. LeVeque:


Show that if $n=rs$, $M_r$ divides $M_n$.

My proof is:

$(M_n=2^n-1)+(n=rs) => (M_{rs}=2^{rs}-1)=>(M_{rs}=(2^r)^s-1)$



In the expansion of $(M_r+1)^s$, all components are of the form $M_rX$, except for the product of all ones. This follows from the combinatorial constraints. Therefore $M_n$ is of the form


Thus $M_r|M_n$.

I have two questions:

1) Is this proof correct/acceptable?

2) In what other ways can this problem be solved? Specifically I am interested in what other kinds of algebraic/logical/mathematical manipulations could be used.

Thanks in advance!

share|cite|improve this question
The proof is good, very clear. I would prefer a few more words. Note that $+$ is not a common abbreviation of the logical connective "and." – André Nicolas Apr 11 '12 at 18:03
@André I'll keep those things in mind. – amr Apr 12 '12 at 2:35
up vote 2 down vote accepted

Note $\rm\ f_n\! :=\ a^n\!-1\ =\ a^{n-m} \: (a^m\!-1) + a^{n-m}\!-1\:$,$\ $ i.e. $\rm\ f_n = k\ f_m + f_{n-m}\equiv f_{n-m}\pmod{f_m}\:$ so

THEOREM $\: $ Let $\rm\ f_n\: $ be an integer sequence with $\rm\ f_{\:0} =\: 0\:\ $ and $\rm\ \: f_n\equiv f_{n-m}\ (mod\ f_m)\ $ for $\rm\: n > m\:$. Then $\rm\:\ (f_n,f_m)\ =\ f_{(n,\:m)}\ \: $ where $\rm\ (i,\:j)\ $ denotes $\rm\ gcd(i,\:j)\:$.

Proof $\ $ By induction on $\rm\:n + m\:$. The theorem is trivially true if $\rm\ n = m\ $ or $\rm\ n = 0\ $ or $\rm\: m = 0\:$.
So we may assume $\rm\:n > m > 0\:$.$\ $ Note $\rm\ (f_n,f_m)\: =\ (f_{n-m},f_m)\ $ follows from the hypothesis.
Since $\rm\:\ (n-m)+m \ <\ n+m\: ,\ $ induction yields $\rm\ \ (f_{n-m},f_m)\ =\ f_{(n-m,\:m)}\ =\ f_{(n,\:m)}\ \ $ QED

In particular $\rm\:(M_R,M_{RS}) = M_{(R,RS)} = M_R\ $ so $\rm\ M_R\:|\: M_{RS}$

See also this post for a conceptual proof exploiting the innate structure - an order ideal, and look up divisibility sequence to learn more about the essence of the matter.

share|cite|improve this answer
Exactly the kind of thing I was looking for, thanks! – amr Apr 12 '12 at 2:32

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.