The definitions and theorems in this section generalize from two variables to finitely many variables.

Definition of GCD, "Greatest Common Divisor"

GCD(a,b)=c means c≥0, c|a and c|b.  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 d|a and d|b, d|GCD(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 d|GCD(a,b)

Definition of LCM, "Least Common Multiple"

LCM(a,b)=c means c≥0, a|c and b|c.  Furthermore, every integer d such that a|d and b|d is also a multiple of c.

In other words,

LCM(a,b)≥0
a|LCM(a,b)
b|LCM(a,b)
for every integer d such that a|d and b|d, LCM(a,b)|d

That 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

Linear Combination Property

If a|b and a|c then a|(bx + cy) for any integers x and y. 

Proof:
Suppose a|b and a|c.
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.

Euclidean Algorithm Property, a.k.a. B�zout's Identity.

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 well-ordering principle.

Let d=xa+yb be the smallest element of S.

Now I'll divide a by d to show that d|a.  By the division algorithm, there are integers q and r such that a=dq+r, and 0≤r<d.

r=a-dq
r=a-(xa+yb)q
r=(1-xq)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 d|a.

Similarly (starting with the division algorithm) we can show d|b.

Thus d is a divisor of a and b.

If c is an integer and c|a and c|b, then by the linear combination property c|(ax+by)

d=ax+by, so c|d.

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.

Related pages in this website

The webmaster and author of this Math Help site is Graeme McRae.