document.write (document.title)

 Math Help > Number Theory > Theorems > Euclid's Algorithm

Well-ordering principle

The well-ordering principle (or well-ordering axiom) is stated as follows:

Every nonempty subset of nonnegative integers contains a smallest element.

Division algorithm, a.k.a. unique division theorem

Theorem: Given integers a and d, d ≠ 0, there exist unique integers, q and r, such that a = qd + r, with 0 ≤ r < |d|

Proof:

Consider the set, S, of all numbers of the form a+nd, where n is an integer.

S = {a - nd : n is an integer}

S contains at least one nonnegative integer, because there is an integer, n, that ensures a-nd ≥ 0, namely

n = -|a| d makes a-nd = a+|a| d2 ≥ a+|a| ≥ 0.

Now, by the well-ordering principle, there is a least nonnegative element of S, which we will call r, where r=a-nd for some n.  Let q = (a-r)/d = (a-(a-nd))/d = n.  To show that r  <  |d|, suppose to the contrary that r ≥ |d|.  In that case, either r-|d|=a-md, where m=n+1 (if d is positive) or m=n-1 (if d is negative), and so r-|d| is an element of S that is nonnegative and smaller than r, a contradiction.  Thus r < |d|.

To show uniqueness, suppose there exist q,r,q',r' with 0 ≤ r,r' < |d| such that a = qd + r and a = q'd + r'.  Subtracting these equations gives d(q'-q) = r'-r, so d|r'-r.  Since 0 ≤ r,r' < |d|, the difference r'-r must also be smaller than d.  Since d is a divisor of this difference, it follows that the difference r'-r must be zero, i.e. r'=r, and so q'=q.

Euclid's algorithm

By the unique division principle, a divided by b gives quotient q and remainder r, such that a = bq+r, with 0 ≤ r < |b|.

Consider now, a sequence of divisions, beginning with a divided by b giving quotient q1 and remainder b1, then b divided by b1 giving quotient q2 and remainder b2, etc.

a=bq1+b1,
b=b1q2+b2,
b1=b2q3+b3,
...
bn-2=bn-1qn+bn,
bn-1=bnqn+1

In this sequence of divisions, 0 ≤ b1 < |b|, 0 ≤ b2 < |b1|, etc., so we have the sequence |b| > |b1| > |b2| > ... ≥ 0.  Since each b is strictly smaller than the one before it, eventually one of them will be 0.  We will let bn be the last non-zero element of this sequence.

From the last equation, we see bn | bn-1, and then from this fact and the equation before it, we see that bn | bn-2, and from the one before that, we see that bn | bn-3, etc.  Following the chain backwards, it follows that bn | b, and bn | a.  So we see that bn is a common divisor of a and b.

To see that bn is the greatest common divisor of a and b, consider, d, an arbitrary common divisor of a and b.  From the first equation, a-bq1=b1, we see d|b1, and from the second, equation, b-b1q2=b2, we see d|b2, etc.  Following the chain to the bottom, we see that d|bn.  Since an arbitrary common divisor of a and b divides bn, we see that bn is the greatest common divisor of a and b.

Theorem: m*GCD(a,b) = GCD(ma,mb)

For any integer, m, m*GCD(a,b) = GCD(ma,mb)

Proof:

By the unique division theorem, if a divided by b gives quotient q and remainder r,

a = bq+r, with 0 ≤ r < |b|

Then ma divided by mb gives the same quotient and remainder mr,

ma = mbq+mr, with 0 ≤ mr < |mb|

and, again, the unique division theorem assures us that q and mr are the unique quotient and remainder of this division.

From Euclid's algorithm,

a=bq1+b1,
b=b1q2+b2,
b1=b2q3+b3,
...
bn-2=bn-1qn+bn,
bn-1=bnqn+1

Multiplying each equation by m, we obtain the result of Euclid's algorithm to find GCD(ma,mb):

ma=mbq1+mb1,
mb=mb1q2+mb2,
mb1=mb2q3+mb3,
...
mbn-2=mbn-1qn+mbn,
mbn-1=mbnqn+1,

proving the result.

Internet references

Mathworld: Well-ordering principle

Wikipedia: Division algorithm, Euclidean algorithm

Related pages in this website

Number Theory Definitions -- Particularly the Euclidean Algorithm Property, a.k.a. B�zout's Identity.

Extended Euclidean Algorithm, and its use in the Chinese Remainder Theorem

The webmaster and author of this Math Help site is Graeme McRae.