Associated Topics || Dr. Math Home || Search Dr. Math

### 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/
```
Associated Topics:
College Number Theory

Search the Dr. Math Library:

 Find items containing (put spaces between keywords):   Click only once for faster results: [ Choose "whole words" when searching for a word like age.] all keywords, in any order at least one, that exact phrase parts of words whole words

Submit your own question to Dr. Math
Math Forum Home || Math Library || Quick Reference || Math Forum Search