
The wellordering principle (or wellordering axiom) is stated as follows:
Every nonempty subset of nonnegative integers contains a smallest element.
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 and ≥ 0, namely
n = a d makes and = a+a d^{2} ≥ a+a ≥ 0.
Now, by the wellordering principle, there is a least nonnegative element of S, which we will call r, where r=and for some n. Let q = (ar)/d = (a(and))/d = n. To show that r < d, suppose to the contrary that r ≥ d. In that case, either rd=amd, where m=n+1 (if d is positive) or m=n1 (if d is negative), and so rd 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 dr'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.
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_{1} and remainder b_{1}, then b divided by b_{1} giving quotient q_{2} and remainder b_{2}, etc.
a=bq_{1}+b_{1},
b=b_{1}q_{2}+b_{2},
b_{1}=b_{2}q_{3}+b_{3},
...
b_{n2}=b_{n1}q_{n}+b_{n},
b_{n1}=b_{n}q_{n+1}
In this sequence of divisions, 0 ≤ b_{1} < b, 0 ≤ b_{2} < b_{1}, etc., so we have the sequence b > b_{1} > b_{2} > ... ≥ 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 nonzero element of this sequence.
From the last equation, we see b_{n}  b_{n1}, and then from this fact and the equation before it, we see that b_{n}  b_{n2}, and from the one before that, we see that b_{n}  b_{n3}, 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, abq_{1}=b_{1}, we see db_{1}, and from the second, equation, bb_{1}q_{2}=b_{2}, we see db_{2}, etc. Following the chain to the bottom, we see that db_{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.
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_{1}+b_{1},
b=b_{1}q_{2}+b_{2},
b_{1}=b_{2}q_{3}+b_{3},
...
b_{n2}=b_{n1}q_{n}+b_{n},
b_{n1}=b_{n}q_{n+1}
Multiplying each equation by m, we obtain the result of Euclid's algorithm to find GCD(ma,mb):
ma=mbq_{1}+mb_{1},
mb=mb_{1}q_{2}+mb_{2},
mb_{1}=mb_{2}q_{3}+mb_{3},
...
mb_{n2}=mb_{n1}q_{n}+mb_{n},
mb_{n1}=mb_{n}q_{n+1},
proving the result.
Mathworld: Wellordering principle
Wikipedia: Division algorithm, Euclidean algorithm
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.