Divisibility Proof by Euclidean Algorithm

Date: 02/20/2003 at 18:04:57
From: Julie
Subject: Number Theory

Let a and b be integers. Suppose that (a,b) = 1 (assuming the gcd 
exists). Prove that there exist integers x and y such that ax + ay = 
1.

Two examples I have worked are: 5x + 11y = (5,11)
(5,11) = 1 so x and y can be several values like x = 1,2,3,...,9 
and y = 1,2,3,4,6,7

and the other one is 175x + 24y = (175,24)= 1
x = 1 and y =1

Date: 02/20/2003 at 18:28:45
From: Doctor Roy
Subject: Re: Number Theory

Hi,

Thanks for writing to Dr. Math.

We can actually prove a much more general fact:

If d = gcd(a,b), then d is the smallest positive integer that can be
written as:

     ax + by = d

for some x and y.

Notice if gcd(a,b) = 1, this is the same statement as the one you wish
to prove.

Let's begin by assuming that g is the smallest positive number that
can be written as ax + by for some x and y, or:

     ax + by = g

Since d divides both a and b, d divides g as well, or:

     d <= g    gcd(a,b) <= g

We have that the gcd(a,b) <= g.

Notice also that g must divide a and g must divide b.

Here's the proof of that fact:

     If g does NOT divide a, then:

     a = u*g + r

where u is some number and r is greater than or equal to 0 and less
than g.

Then:

     r = a - ug

But g = ax + by:

     r = a - aux - buy

       = a*(1 - ux) + b*(-uy)

But this violates the condition that g is the SMALLEST positive number
that can be written as a linear combination of a and b unless r = 0.
But if r = 0, g divides a.  If g divides a, it must also divide the
greatest common divisor, or:

     g <= GCD(a,b)

So, we have: 

    g <= gcd(a,b) and  g >= gcd(a,b)

The only way this is true is if g = gcd(a,b) = d.

So, we have our proof.

Does this help?  Please feel free to write back with any questions you
may have.

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

Date: 02/20/2003 at 20:38:32
From: Julie
Subject: Number Theory

Thank you for help so far; however, I do not completely understand it 
yet. I have a couple more questions.  I do not understand the 
difference between the numbers d and g. I also do not understand the 
proof that g does not divide a. How does this violate the condition 
that g is the smallest positive number? Also I know the Euclidean 
Algorithm is a = nq+r; how do you use this to solve for x and y in 5x 
+11y = 1?

Thanks again.
Julie

Date: 02/21/2003 at 12:21:30
From: Doctor Roy
Subject: Re: Number Theory

Hi,

The idea is that d is what we KNOW is gcd(a,b). We want to show that
g is equal to d. We do NOT know that this is true.

We want to prove that d = g.  But we cannot be sure of that. So, we
have to show it.

We want to show that g DOES divide a. It has to. We know the Euclidean 
algorithm:

    a = ng + r

We want to show that r must be equal to 0 or else we get a 
contradiction. If r = 0, then g | a.

r must be at least 0 and less than g. The remainder (that's what r
is) is never greater than the divisor.  

For example, if we have

    41/11 = 3 remainder 8

Notice the remainder is 8.  It cannot be equal to 11.  

So, if we assume that g is the smallest possible number that can be
written as:

    g = ax + by

let's find the remainder when we divide a by g

    a = n*g + r

r must be less than g and at least 0.  If r is equal to g, we have
made a mistake in writing the division algorithm.

If a = n*g + r, we can substitute:

    a = n*g + r

    g = ax + by


  =>  Plug g into the first equation:

    a = n*(ax + by) + r

    a = nax + nby + r

    r = a - nax - nby

    r = a*(1 - nx) - b*ny

Notice that r is a linear combination of a and b. So, r is a non-
negative number that can be written in the form:

   r = a*Z + b*W

where Z = (1 - nx) and W = -ny.

But we already said that g was the SMALLEST positive number that could
be written this way. This means that r is NOT positive or else g is 
not the SMALLEST positive number, because r must be less than g. That
means that r must be zero.

If r = 0, then:

    a = n*g + r

    a = n*g

This means that g divides a. Using a similar proof, g divides b. If g 
divides both a and b, then g MUST divide gcd(a,b). Every divisor of 
both a and b divides the gcd. So,

    g <= gcd(a,b)

And we have already shown that:

    g >= gcd(a,b)

The only way both statements are true is if g = gcd(a,b).
   
- Doctor Roy, The Math Forum
  http://mathforum.org/dr.math/