CONGRUENCE 99
For example: 182(X) 126 = (26- 7)@(18 7)) = (26 18)-7
= 2elioe
232. Th. a-=0~b—-= 02 (ab) R (ac) = |a|(®R¢)

233. Th. b—-=0~c-=0~all b>D (ac) R (bc) = |c|;
and conversely, if (ac) X (bc) = |c|, then a 1] b.

234. Th. a3 c~bFc—~b—=0D
a®@b3>c~@®b) :|c| =@:c) R0 :¢)

We have ¢ = gc and b = x¢, where x —=

Hence a @ b = (gc) R (xc) = (¢XR x)|¢| : S 230
Therfor a Qb >> ¢
and (@ @0b) : [c] =¢Rx=(@:c) R :0)

235. Th. If b—= 0 and |k| = a (XD, then a > h, b > h,
and a :h 11 b : h; and conversely, if b—= 0,a >> h,b >> h, and
a:hl1lb:h,then k| = aXb.

For the direct theorem

(a k)0 (b k) =ECH0y: [k =1 § 234.
Hence ashllib:h §171.

For the converse theorem reverse the steps.
This theorem is equivalent to the following.

236. Th. If a and b are two integers, not both zero; then, if
k s their greatest common factor, there exist two integers ¢ and d,
prime to each other, such that a = kc and b = kd; and con-
versely, if a = kc and b = kd, where ¢ and d are prime to each
other, k positiv, and d not zero, then k is the greatest common
factor of a and b.

237. Th. The common factors of two integers, not both zero,
are the same as the factors of theiwr greatest common factor.

For, by § 65, every factor of the greatest common factor is
a factor of each of the given integers.

And, by § 234, every common factor of the two given integers
is a factor of their greatest common factor,