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 ab, 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.


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.



About shivang1729

I am a young student who loves math . I like number theory and inequalities part the most , and preparing for Math Olympiads :)

Posted on Monday,February 13, 2012, in Greatest common divisor and tagged , , , . Bookmark the permalink. Leave a comment.

Comments / doubts/answers here:

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: