Greatest Common Divisor

The Greatest Common Divisor or gcd is the largest common factor between two numbers. In what follows, I will write this as function such as gcd(9,6) = 3. The gcd cannot be applied to 0.

For example, the gcd(2,4) = 2 and gcd(5,7)=1.

One assumption that I will use below is the Well Ordering Principle.

Postulate 1: Well Ordering Principle

For any set of positive integers, one value is the lowest.

For a small set of numbers, this principle is clearly true.

For the set of all negative numbers, it is not true. No matter which negative number we choose, we can always find another negative number which is lower.

For the set of all positive numbers, it is true. It is 1. Likewise, it is true for all subsets of this set.

This principle is normally called a postulate. A postulate is an assumption that mathematicians use without proof. It is the foundation of a proof.

Lemma 1: Bezout's Identity: If gcd(a,b) = c, then there exists s,t such that: c = as + bt.

(1) Let S be a set { am + bn : m,n are integers, am + bn > 0 }

In other words, let S be the set of all sums that can be created from am + bn. This includes (1)m + (1)n, (2)m + (1)n, etc. It includes any combination. So, we can also assume that (1000)m + (99)n are elements of this set if the sum is greater than 0.

(2) This set is not empty

In other words, for any a, b, we know that there is at least one element in this set.

If a + b > 0, then choose m=1,n=1.

If a + b = 0, then either a or b is negative. Let's assume a. Then choose m=-1,n=1.

If a + b is less than 0, then either a or b is the lowest. Let's assume a. Then choose m=-1,n=1.

(3) We know that one of these elements in the set is the smallest. [By the Well Ordering Principle]

(4) Let's call the smallest element d.

(5) d divides both a,b.

I will now show that d divides a. The same argument will also apply to b.

We know that there exists q,r such that a = dq + r where r is a positive integer less than d. [By the Division Algorithm]

In other words, q is the quotient and r is the remainder.

r = a - dq = a - (as + bt)q = a - asq - btq = a(1 - sq) - btq = a(1-sq) + b(-tq).

Assume that r > 0.

Then a(1 - sq) + b(-tq) is an element of the above set.

But this is a contradiction. d is the lowest element and yet here is an element smaller than d.

So, r = 0.

(6) d is the gcd for a,b.

Let d' = gcd(a,b)

Let's define h,k: a = d'h, b = d'k

So, d = as + bt = (d'h)s + (d'k)t = d'(hs + kt)

Which means d' divides d.

So, d' = d since d' is the gcd.

QED

Lemma 2: For all pairs of numbers, it is possible to reduce them to a form that is coprime.

(1) Assume that we have two numbers: x, y that are not coprime.
(2) Then there exists d such that d = gcd(x,y) and d > 1.
(3) Then there exists X,Y such that x = dX, y = dY.
(4) And finally, gcd(X,Y)=1

(a) Assume gcd(X,Y) = D and D > 1
(b) Then there exists a,b such that X = aD, Y = bD.
(c) And x = d(aD), y = d(bD)
(d) From this, we see that dD divides both x and y.
(e) We also know dD > d since d > 1 and D > 1.
(f) But this is a condradiction since d is the greatest common denominator.
(g) So we reject our assumption.

QED