98 SPECIAL TOPICS IN THEORETICAL ARITHMETIC

Def. As thus restricted, and for positiv integers, the
method of finding the greatest common factor described above
has been called the Algorithm of Euclid (1).

It would seem appropriate to give the same name to the
more general method described in § 226.

230. Th. If in applying the algorithm of Euclid the divisor
that gives the zero remainder is numerically equal to unity, then
the two given numbers are prime to each other, and conversely.

Example.

23 11 17

 

231. Th. b—-=0~c—= 02 (ac) R (bc) = (a R b)|c|.

Let 71, 7o, 73, *+*, 7a_1, 7» be a series of numbers of which
only the last is zero and such that of any three successiv num-
bers in the series

&0 Py e, T 7, fany T

the first is congruent to the third with respect to the second.
Then in the series ac, bc, ric, 3¢, 7sc, * * +, ¥n_C, ¥»¢ the same

is tru. § 216.
Hence (a¢) ® (b)) = |7asc| = ranllc] = @@ )]

In finding the greatest common factor of two numbers, if
any common factor, except 1 or — 1, is known, the work may
be simplified by taking out this common factor from the two
numbers, getting the greatest common factor of the quotients,
and multiplying this greatest common factor by the numerical
value of the factor taken out.

(1) See Euclid, Elements of Geometry, Bk. VII, Prop. 2.