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
1 and d are greatest common divisors of a and b. Then d
1|a and d
1|b and if c|a and c|b, then c|d
1. But d is also a greatest common divisor, so d|a and d|b, so d|d
1. Similarily d
1|d. Thus d
1=ds and d=d
1t for integers s and t. So d=d
1t=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
1=d(1) and d
1=d.
Q.E.D.