greatest common divisor (idea)

Definition: Let a and b be integers (both not 0). A positive integer d is the greatest common divisor (GCD) of a and b if:
1) d|a and d|b
2) If c|a and c|b, then c|d.

Definition: If x and y are positive integers, x is a divisor of y, denoted x|y, if xq=y for some integer q.

Theorem: Let a and b be integers (not both 0), then a greatest common divisor d of a and b exists and is unique. Moreover there exists integers x and y such that d=ax+by.

Proof: We must first show that and integer d is a common divisor of a and b. Let a and b be integers, not both 0. Let S={n>0|n=ax+by for integers x and y}. Notice that a=a(1)+b(0) and b=a(0)+b(1), so a and b are elements of S. Further, -a=a(-1)+b(0) and -b=a(0)+b(-1), so -a and -b are in S. So S contains at least 1 positive integer.

By the Well Ordering Principle, S has a least element, namely d. Since d is in S, there are integers x and y such that d=ax+by. Now, by the Division Algorithm, to divide by d there must be integers q and r such that a=d*q+r where 0<=r<d. Thus r=a-d*q=a-(ax+by)q=a(1-x)+b(-qy). Therefore r is in S. Since d is the least element of S, we conclude that r=0. Then a=dq and d|a. Similarily, d|b. Thus d is a common divisor of a and b.

Now we must prove that d is the greatest common divisor of a and b. Assume that c is a common divisor of a and b. Then a=cu and b=cv for integers u and v. So d=ax+by=(cu)x+(cv)y=c(ux+vy). Thus c|d. Hence d is the greatest common divisor of a and b.

We must now show that d is unique. Suppose d₁ and d are greatest common divisors of a and b. Then d₁|a and d₁|b and if c|a and c|b, then c|d₁. But d is also a greatest common divisor, so d|a and d|b, so d|d₁. Similarily d₁|d. Thus d₁=ds and d=d₁t for integers s and t. So d=d₁t=dst which implies d=d(st). So 0=d(st)-d=d(st-1) which implies either d=0 or st-1=0. But d cannot be 0 since d is a positive integer, so st-1=0 which implies st=1. Thus s=t=1 or s=t=-1. So d₁=d(1) and d₁=d. Q.E.D.