An Inductive ProofDate: 02/13/2003 at 23:08:21 From: Mark Subject: Number Theory If gcd(n,m) = 1, then prove gcd(Rn,Rm) = 1. Rn,Rm are repunits. Do you go with the assumption that d = s(Rn) + t(Rm)? Do you follow that path for the proof? Date: 02/14/2003 at 02:30:20 From: Doctor Jacques Subject: Re: Number Theory Hi Mark, Let b be the number base. As R_m = (b^m - 1)/(b - 1), we see that gcd(R_m, b) = 1. Indeed, if d divides R_m, d also divides (b^m - 1), and cannot therefore divide b. Assume gcd(m,n) = 1, and m < n. We have: R_n = b^m * R_(n-m) + R_m If d is a common factor of R_m and R_n, b divides b^m * R_(n-m), and, by what has just been said, b divides R_(n-m). Note also that gcd (m, n-m) = 1. You can now repeat the process, exactly as in the Euclidean algorithm, and reach the conclusion that d divides R_1 = 1, and therefore that d = 1. This is in fact an inductive proof, with induction on m (the smaller number). Please feel free to write back if you need further help. - Doctor Jacques, The Math Forum http://mathforum.org/dr.math/ |
Search the Dr. Math Library: |
[Privacy Policy] [Terms of Use]
Ask Dr. Math^{TM}
© 1994-2015 The Math Forum
http://mathforum.org/dr.math/