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

### Euclid's Algorithm for Finding a GCD

```Date: 10/12/2002 at 15:36:06
From: Matt
Subject: Factoring a large number

We were given the numbers 163231, 152057, and 135749, and were asked
to find the only number besides one that is a common factor.

What is the best way to do this since these are large numbers?
Thanks.
```

```
Date: 10/12/2002 at 16:47:49
From: Doctor Ian
Subject: Re: Factoring a large number

Hi Matt,

You could use Euclid's algorithm for finding the greatest common
divisor of any two of the numbers.

163231 = 135749*1 + 27482
|         |
|         +-----------+
+---------------+     |
|     |
gcd(16321,135749) = gcd(135749,27482)

135749 = 4*27482 + 25821

gcd(135749,27842) = gcd(27482,25821)

27482 = 25821*1 + 1661

gcd(27482,25821) = gcd(25821,1661)

25821 = 1661*15 + 906

gcd(25821,1661) = gcd(1661,906)

1661 = 906*1 + 755

gcd(1661,906) = gcd(906,755)

906 = 755*1 + 151

gcd(906,755) = gcd(755,151)

755 = 151*5

gcd(755,151) = 151

And lo and behold,

135749 = 151 * 899

163231 = 151 * 1081

And this should put you well on your way to dealing with the third
number.

Does this help?

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

```
Date: 10/12/2002 at 22:24:39
From: Matt
Subject: Factoring a large number

Thanks a lot! I used the formula and I got 151 for all three numbers.

How could you find three numbers, small or pretty large like those,
that only have one common divisor?

Thanks, Matt
```

```
Date: 10/12/2002 at 23:06:10
From: Doctor Ian
Subject: Re: Factoring a large number

Hi Matt,

Do you mean, how would you set up a problem like this? You obviously
need three numbers like

a = 151 * this
b = 151 * that
c = 151 * the_other

and as long as this, that, and the_other have no factors in common,
a, b, and c will have only the one factor in common.

Does that make sense?

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

```
Date: 10/14/2002 at 10:05:34
From: Matt
Subject: Factoring a large number

Yes, I want three numbers that have only one divisor, but is there a
formula or a pattern I should look for that would clue me that these
numbers would only have one divisor?

Thanks, Matt
```

```
Date: 10/14/2002 at 10:35:34
From: Doctor Ian
Subject: Re: Factoring a large number

Hi Matt,

There are divisibility rules that you can use to check for
divisibility by small numbers, which you can read about in our FAQ:

http://mathforum.org/dr.math/faq/faq.divisibility.html

And of course, you should always check those first. But if someone
goes to the trouble of setting up a problem like this, it's unlikely
that he'll choose such small numbers as the common divisor.

One of the things that makes prime numbers so interesting is that they
look just like composite numbers, and there appear to be no patterns
that can be used to identify them without doing a lot of divisions.
It's exactly what makes them useful for encryption.

- Doctor Ian, The Math Forum
http://mathforum.org/dr.math/
```
Associated Topics:
Middle School Factoring Numbers
Middle School Prime Numbers
Middle School Puzzles

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