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

### 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/
Associated Topics:
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