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

### Euclidean Algorithms

```
Date: 3/13/96 at 8:44:27
From: John Vogler
Subject: Number Theory

Dear Dr. Math,

What is the Euclidean algorithm?  What is a "constructible" number?

What can you tell me about Diophantine equations?  I know that one
is an equation in several variables which must be solved for integer
solutions (or rational, perhaps positive numbers only).  I understand
that high-order Diophantine equations are pretty much solved one by
one by no general procedure, but that there is a procedure for
solving single-order equations.  Do you know it?

A "perfect" number is equal to the sum of its factors excluding itself;
6 = 1+2+3.  What is the significance of a perfect number?  Primes
are nice for prime factorization, but I don't see any use for perfect
numbers.

Curious,
Johnny Vogler
```

```
Date: 3/24/96 at 12:17:23
From: Doctor Ken
Subject: Re: Number Theory

The Euclidean Algorithm is a procedure for finding the gcd of two
numbers.  Basically I'll give you an example because it's harder to
explain than to show:

Take 5033464705 and 3137640337, find their greatest common
divisor.

To do this we use the Euclidean Algorithm:

5033464705 = 1*3137640337 + 1895824368

3137640337 = 1*1895824368 + 1241815969

1895824368 = 1*1241815969 + 654008399

1241815969 = 1*654008399 + 58200938

654008399 = 1*58200938 + 66200829

58200938 = 8*66200829 + 58200938

66200829 = 1*58200938 + 7999891

58200938 = 7*7999891 + 2201701

7999891 = 3*2201701 + 1394788

2201701 = 1*1394788 + 806913

1394788 = 1*806913 + 587875

806913 = 1*587875 + 219038

587875 = 2*219038 + 149799

219038 = 1*149799 + 69239

149799 = 2*69239 + 11321

69239 = 6*11321 + 1313

11321 = 8*1313 + 817

1313 = 1*817 + 496

817 = 1*496 + 321

496 = 1*321 + 175

321 = 1*175 + 146

175 = 1*146 + 29

146 = 5*29 + 1

29 = 29*1 + 0

So 1 is the greatest common divisor of 5033464705 and
3137640337.

We could have gotten the gcd by factoring into primes and then
getting the smallest power of each prime in both of them and
multiplying together - but factoring those numbers would not be fun.
In fact if the numbers got real large, say if they were about a
hundred digits long, Ron Rivest (at MIT) conjectured it would take
4 BILLION years to factor the numbers into primes, while finding
the gcd this way would only take a couple of months (or less).

So you see the Euclidian Algorithm is a pretty powerful thing.

Diophantine equations are just that - equations in one or more
variables which look for positive integer (or rational in some
instances) solutions.

Let ax + by = c, where a, b are given integers and x, y are
unknown integers.  Suppose at least one of a, b is not zero.  Then let
g = gcd(a,b).  If g does not divide c then there are no solutions to
this problem.

But say g divides c.  Then by the Euclidean algorithm we can find
two integers x_0, and y_0 such that a*x_0 + b*y_0 = g. (This is
much trickier than just explaining the Euclidean algorithm, so if
you'd take my word for it I'd be happy :) .)

Multiply both sides of this equation by c/g.  Since g divides c this is
an integer.  Multiplying we get:

a*(c*x_0)/g + b*(c*y_0)/g = c.

So x = c*x_0/g, and y = c*y_0/g is an integer solution to this
problem.

Let's see if we can get any more solutions (there might be more than
one).

Rename the above solution to x_1 = c*x_0/g, and y_1 = c*x_0/g.
We can get more solutions by setting x = x_1 + k*b/g, and y =
y_1 - k*a/g, where k is an arbitrary integer.  Now are there any
solutions that don't fit this form?  The answer is no; to prove this say
x_1, y_1, some other two integers x and y are both solutions.  Then
ax + by = ax_1 + by_1. So a(x - x_1) = b*(y_1 - y).  Divide by g on
both sides to get:

(a/g)*(x-x_1) = (b/g)*(y_1-y).

This means (a/g) divides what's on the right hand side.  But (a/g)
does not divide (b/g) since they are relatively prime (since g is the
gcd of them), so (a/g) divides (y_1 - y). So k*(a/g) = y_1 - y.
Solving this for y we get:

y = y_1 - k*(a/g).

Then substituting in we get:

x = x_1 + k*(b/g).

So we've proved that every solution is of that form.

For higher order problems it gets a little tricky.  Normally they're
examined by using modular analysis, which means you reduce the
coefficients modulo a prime and check to see if it's possible, and if it
is, what the possibilities are.  Basically this technique is not very
hard, but it requires a lot of background knowledge and good logic
skills, so it'll be pretty hard to explain here. (Notice how hard it was
to explain the first order.)

Perfect numbers are basically just that, pretty to think about, but not
very useful.  Although many theorems that help us factor large
numbers come from the study of perfect numbers.  An example of
this is Euler's proof that any divisor of a number of the form
2^2^n - 1 is of the form  k*2^n - 1.  (Example: 2^2^5 - 1 =
2^32 = 4294967295 = 16843009 * 255).

I hope this helps and that you didn't get too bored reading the
procedure for finding the solution to the first order Diophantine
equations.

-Doctor Steven,  The Math Forum
```
Associated Topics:
College Algorithms
College Definitions
College Number Theory
High School Definitions
High School 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