# Simple Mersenne prime divisibility proofs

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.

-
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

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.

-
Exactly the kind of thing I was looking for, thanks! – amr Apr 12 '12 at 2:32