The greatest common divisor of two numbers
and
may be found from the prime – power factorizations ofandare known. Considerable computing power may be needed to find the prime power factorizations however and there is a procedure – Euclid's algorithm - that requires less computation.
We need the following theorem
Theorem 1 The Division Algorithm
Given two numbersandwith
there exists a unique pair of integers
called the quotient and
called the remainder such that
with
Moreover,
if and only ifdivides
Proof: Let
be the set of nonnegative integers given by
This is a nonempty set of nonnegative integers so it has a smallest member, say
Let
then 
and
Now we show that
Assume
then
but
since
hence
is a member ofsmaller than it's smallest member,
This contradiction shows thatThe pair
is unique for if there were another such pair, say
then
so
hence
divides
If
then 
a contradiction therefore
and
Finallyif and only ifdivides 
The above theorem gives us a method for finding q and r. We subtract from or add to a enough multiples of b until we have found the sammlest nonnegative number of the form a-bx.
Theorem 2 The Euclidean Algorithm
Given positive integers a and b where
let r-0 =a and r-1 =b and apply the division algorithm repeatedly to obtain a set of remainders r-2 , r-3 , ..., r-n , r-{n+1} defined recursively by the relations
Then
the last nonzero remainder in this process, is
the greatest common divisor of a and b.
Proof: There is a stage at which
because the
are decreasing and nonnegative. The last relation
shows that
divides
The next to last shows thatdivides
so by induction
divides each
In particular
and
sois a common divisor ofand
Letbe any common divisor ofand
The definition of
shows that
dividesthen the line below shows thatdivides
so by inductiondivides eachso divideshence
Example: Find the greatest common divisor of 19 and 7.
(1)
(2)
(3)
The greatest common divisor of 19 and 7 is thus 1.
We can use the Euclidean algorithm to write the greatest common divisor of two numbers
and
as a linear combination ofand
For the example above
and
we have from (3)
(4)
Rearrange (2) to give
and substitute into (4)
(5)
Rearrange (1) to give
and substitute into (5)
which rearranges to give