Greatest Common Factor of Numbers Composed of All Ones

Date: 06/30/2008 at 01:51:17
From: Ori
Subject: gcd(111..111,1111...111)

I need to compute this gcd, so far I got Fibonacci numbers in the subs 
(the Euclidean algorithm) but I can't get to the end.

Date: 06/30/2008 at 11:40:33
From: Doctor Ali
Subject: Re: gcd(111..111,1111...111)

Hi Ori!

Thanks for writing to Dr. Math.

If I understand correctly, you want to evaluate the greatest common
divisor of two numbers which are made up only of 1's and they have a
difference in just one 1.  Please let me know if I'm on the wrong track!

Firstly note that we can write,

  111....111
  \________/
     n 1's

in a more mathematical form as,

   10^n - 1
  ----------
       9

Do you see why?  We simply subtract one from powers of ten, which
makes n consecutive 9's.  Dividing the result by 9 turns all the 9's
into 1's.  Does that make sense?

I just said this so that it _may_ help us!

Let's make a table of different cases that can happen.  I'll make the 
table for,

  g = GCD ( 111...1  ,  1111...1)
            \_____/     \______/
             n 1's     (n+1) 1's

I iterated n from 1 to 10 using math software and here is the result:

  +-----+-----+
  |  n  |  g  |
  +-----+-----+
  |  1  |  1  |
  +-----+-----+
  |  2  |  1  |
  +-----+-----+
  |  3  |  1  |
  +-----+-----+
  |  4  |  1  |
  +-----+-----+
  |  5  |  1  |
  +-----+-----+
  |  6  |  1  |
  +-----+-----+
  |  7  |  1  |
  +-----+-----+
  |  8  |  1  |
  +-----+-----+
  |  9  |  1  |
  +-----+-----+
  | 10  |  1  |
  +-----+-----+

So, it seems that they are always relatively prime!  Now let's try to 
prove it.

We know that,

  GCD( a , b ) = GCD( a , b - 10 a )

You can put any other number instead of 10, but in this problem, 10 
helps a lot.

  g = GCD ( 111...1  ,  1111...1)
            \_____/     \______/
             n 1's     (n+1) 1's

Using the above fact,

  g = GCD ( 111...1  ,  1111...1  -  10 x 111...1 )
            \_____/     \______/          \_____/
             n 1's     (n+1) 1's           n 1's


Now, just note that the second argument equals one.  So we have,

  g = GCD ( 111...1  ,  1 )
            \_____/
             n 1's

We know that GCD of any number and one equals one.  So,

      g = 1

So, we proved that they are always relatively prime!

Does that make sense?  Please write back if you still have any
difficulties.

- Doctor Ali, The Math Forum
  http://mathforum.org/dr.math/