The theory of numbers, by Robert D. Carmichael ...

18

THEORY OF NUMBERS

~ 9. THE GREATEST COMMON FACTOR OF TWO OR MORE
INTEGERS
Let in and n be two positive integers such that in is greater
than in. Then, according to the fundamental theorem of
Euclid, we can form the set of equations
m=qn+-ni, o <II <n,
n = q21i +~112, 0 <12 <112,
nl = q2n2+n3, O <n3<11n2,
ilk-2=-qk-lI1IA-i +k, O<nk<n1 —l,
oik- = qkn7k.
If m is a multiple of n we write n no, k =o, in the above equations.
DEFINITION. The process of reckoning involved in
determining the above set of equations is called the Euclidian
Algorithm.
I. The number nH to which the Eiclidian algorithm leads is
the greatest common divisor of mI and n.
In order to prove this theorem we have to show two things:
i) That nk is a divisor of both im and n;
2) That the greatest common divisor d of in and n is a
divisor of nk.
To prove the first statement we examine the above set of
equations, working from the last to the first. From the last
equation we see that nk is a divisor of 1k-1. Using this result
we see that the second member of next to the last equation is
divisible by nki Hence its first member nk-2 must be divisible
by is1. Proceeding in this way step by step we show that
n2 and nl, and finally that n and m, are divisible by n,.
For the second part of the proof we employ the same set of
equations and work from the first one to the last one. Let
d be any common divisor of in and n. From the first equation
we see that d is a divisor of ni. Then from the second equation
it follows that d is a divisor of n2. Proceeding in this way we