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.

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

$M_n=2^n-1$.

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

$(M_r=2^r-1)=>(M_r+1=2^r)$

$M_{rs}=(M_r+1)^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

$M_n=M_{rs}=M_r(X_1+X_2+...)+1-1$.

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|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
add comment

1 Answer 1

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|improve this answer
    
Exactly the kind of thing I was looking for, thanks! –  amr Apr 12 '12 at 2:32
add comment

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.