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

### 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/
```
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