An Inductive Proof

Date: 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/