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| d² ≥ 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 q₁ and remainder b₁, then b divided by b₁ giving quotient q₂ and remainder b₂, etc.

a=bq₁+b₁,
b=b₁q₂+b₂,
b₁=b₂q₃+b₃,
  ...
b_n-2=b_n-1q_n+b_n,
b_n-1=b_nq_n+1 

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

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

To see that b_n is the greatest common divisor of a and b, consider, d, an arbitrary common divisor of a and b.  From the first equation, a-bq₁=b₁, we see d|b₁, and from the second, equation, b-b₁q₂=b₂, we see d|b₂, etc.  Following the chain to the bottom, we see that d|b_n.  Since an arbitrary common divisor of a and b divides b_n, we see that b_n 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=bq₁+b₁,
b=b₁q₂+b₂,
b₁=b₂q₃+b₃,
  ...
b_n-2=b_n-1q_n+b_n,
b_n-1=b_nq_n+1 

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

ma=mbq₁+mb₁,
mb=mb₁q₂+mb₂,
mb₁=mb₂q₃+mb₃,
  ...
mb_n-2=mb_n-1q_n+mb_n,
mb_n-1=mb_nq_n+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.