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

### Using Euclid's Algorithm with Three Numbers

```Date: 11/05/2003 at 00:03:45
From: An
Subject: how do i find the gcd of 3 integers using Euclid's Algorithm

How do I find the GCD of three integers using Euclid's Algorithm?  I
know how to use it with 2 numbers but not 3.  I am not sure where you
plug the third integer into the algorithm.  What do you subtract from
the second or third integer?

```

```
Date: 11/05/2003 at 16:52:15
From: Doctor Rob
Subject: Re: how do i find the gcd of 3 integers using Euclid's Algorithm

Thanks for writing to Ask Dr. Math, An!

One approach is to first use the algorithm to find the GCD d of the
first two numbers, then use the algorithm to find the GCD of d and the
third number.

This works because GCD(x,y,z) = GCD(GCD(x,y),z).

Another approach is to start with three numbers x, y, and z.  Label
them so that z is the smallest.  Divide

x = Q1*z + R1,  0 <= R1 < z,
y = q1*z + r1,  0 <= r1 < z.

Then replace x and y by R1 and r1, relabel the numbers x, y, and z, so
that the new z is the smallest nonzero number of the three, and
repeat.  Continue until both remainders are zero.  Then the last z
will be the GCD of all three numbers.

Example:  Find the GCD of 203, 91, and 77.

original {x,y,z} = {203,91,77}
203 = 2*77 + 49,
91 = 1*77 + 14,

new {x,y,z} = {77,49,14},
77 = 5*14 + 7,
49 = 3*14 + 7,

new {x,y,z} = {14,7,7},
14 = 2*7 + 0,
7 = 1*7 + 0,

Both remainders are 0, so GCD = last z = 7.

GCD is 7.

Feel free to write again if I can help further.

- Doctor Rob, The Math Forum
http://mathforum.org/dr.math/
```
Associated Topics:
High School Basic Algebra
Middle School Algebra
Middle School Factoring Numbers

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