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

_{1}t for integers s and t. So d=d

_{1}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

_{1}=d(1) and d

_{1}=d.

Q.E.D.