SECTION 2.1 Elementary Number Theory 57
Now letr be the smallest element of this set; note thatr≥0, and let
qbe defined so thatr=b−qa. Therefore, we already haveb=qa+r.
Notice that ifr6≤a, then we may setr′=r−a≥0 and so
r′=r−a−a=b−qa−a=b−(q+ 1)a.We see, therefore, thatr′∈S; sincer′≥0 this contradicts our choice
ofrin the first place!
Next, we shall show that the quotient and remainder are unique. There-
fore, assume that
b=qa+r=q′a+r′, where 0≤r, r′< a.Therefore we conclude that (q−q′)a=r′−r. Since 0≤r′,r < awe
see that|r′−r|< aand so|(q−q′)a|=|r′−r|< awhich clearly forces
q−q′= 0. But thenr′=rand we’re done!^2
In the above, ifr= 0, and sob=qa, we say thata dividesband
writea|b.
If a, b ∈ Z and not both are 0, we say that the integer d is the
greatest common divisorofaandbif
(i)d > 0
(ii)d|aandd|b,(iii) if alsod′|aandd′|band ifd′>0, thend′≤d.Example. In small examples, it’s easy to compute the greatest com-
mon divisor of integers. For example, the greatest common divisor of
24 and 16 is easily seen to be 4. In examples such as this, the greatest
(^2) The assumption in the theorem thataandbare both non-negative was made only out of
convenience. In general, the division algorithm states that for two integersa, b∈Z, witha 6 = 0,
there exist unique integersqandrsuch that
b=qa+r, where 0≤r <|a|.