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!
Answer
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.
No comments:
Post a Comment