
The definitions and theorems in this section generalize from two variables to finitely many variables.
GCD(a,b)=c means c≥0, ca and cb. Furthermore, every integer d that divides a and b also divides c.
To put it another way, here are the properties of GCD, in a nutshell  this form is useful for proofs, because it provides a checklist of things you must show in order to establish GCD(a,b) as well as a set of facts you know if you know GCD(a,b):
GCD(a,b)≥0
GCD(a,b)a
GCD(a,b)b
for every integer d such that da and db, dGCD(a,b)That last item in the checklist is equivalent to the following statement:
for all integers d, it is true that da or db or dGCD(a,b)
LCM(a,b)=c means c≥0, ac and bc. Furthermore, every integer d such that ad and bd is also a multiple of c.
In other words,
LCM(a,b)≥0
aLCM(a,b)
bLCM(a,b)
for every integer d such that ad and bd, LCM(a,b)dThat last item in the checklist is equivalent to the following statement:
for all integers d, it is true that ad or bd or LCM(a,b)d
If ab and ac then a(bx + cy) for any integers x and y.
Proof:
Suppose ab and ac.
Then integers q and r exist such that b = aq and c = ar.
So, for any integers x and y, bx + cy = a(qx + ry)
and qx + ry is an integer, and hence a(bx + cy).
An application of Linear Combination is this:
GCD(m,n)=GCD(m+kn,n), where k is any integer.
Proof:
GCD(m+kn,n)n and GCD(m+kn,n)m+kn, by the definition of GCD.
GCD(m+kn,n)(m+kn)kn, by the linear combination property
GCD(m+kn,n)m
GCD(m+kn,n)GCD(m,n)
similarly, GCD(m,n)GCD(m+kn,n)
so GCD(m,n)=GCD(m+kn,n), where k is an integer.
For any integers a and b, there exist integers x and y such that GCD(a,b)=ax+by.
If a and b are zero, then x=y=0, and the property is obviously true. Now we can assume a or b is nonzero.
Let S be the set of positive integers of the form sa + tb, where s and t are integers.
Set S isn't empty so it has a smallest element by the wellordering principle.
Let d=xa+yb be the smallest element of S.
Now I'll divide a by d to show that da. By the division algorithm, there are integers q and r such that a=dq+r, and 0≤r<d.
r=adq
r=a(xa+yb)q
r=(1xq)a + (yq)b,which has the form of elements of S, so either r=0 or r is in S.
But r can't be in S, because r<d, the smallest element of S. So r=0.
a=dq+r, so a=dq, so da.
Similarly (starting with the division algorithm) we can show db.
Thus d is a divisor of a and b.
If c is an integer and ca and cb, then by the linear combination property c(ax+by)
d=ax+by, so cd.
Any number that divides a and divides b also divides d, so d=GCD(a,b)
A constructive algorithm to find the integers x and y is the Extended Euclidean Algorithm.
The converse: GCD(a,b)ax+by is a consequence of the linear combination property.
In particular, if x and y exist such that ax+by=1, then GCD(a,b)1, so GCD(a,b)=1.
The webmaster and author of this Math Help site is Graeme McRae.