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.

For your linear problems:

   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