Ifdivides two integers
and
then
is called a common divisor of
and
Hence 1 is a common divisor of any two numbers
and
Every pair of integers
and
has a divisor
which can be expressed as a linear combination
of
and
Because
divides and b, d divides every linear combination
of a and b. Moreover, every common divisor of
and
divides this
Proof: AssumeWe use induction on
where
If
then
and we can take
with
Assume then that the theorem has been proved for
By symmetry we can assume
If
take
If
apply the theorem to
and
Since
the induction assumption is applicable and there is a common divisor
of
and
of the form
This
also divides
so
is a common divisor of
and
and we have
a linear combination of
and
To complete the proof we need to show that every common divisor divides
but a common divisor divides
and
and hence by linearity divides
If
or
or both we can apply this result to
and
Moreoveris unique and is the greatest common divisor, gcd, of
and
has the following properties where
a)
b)
c)
d)and
Proof
a)implies
and
for some
so
The same argument with
and
and
interchanged implies
therefore
and
b)implies there exist
such that
then there exists also
such that
therefore
Now interchange
with
and
with
with the same reasoning to get
Hence
and
c)Letand let
Write
then
(1) and so
because
divides both
and
Also (1) shows that
and
Hence



Proof: Sincewe can write
Therefore
But
and
so