The Math Forum

Ask Dr. Math - Questions and Answers from our Archives
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 

Please feel free to write back if you need further help.

- Doctor Jacques, The Math Forum 
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

[Privacy Policy] [Terms of Use]

Math Forum Home || Math Library || Quick Reference || Math Forum Search

Ask Dr. MathTM
© 1994- The Math Forum at NCTM. All rights reserved.