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 d
a 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
