106 II Divisibility
Heilbronn and Linfoot (1934) showed that there was at most one additional negative
value ofdfor whichOdis a principal ideal domain. Stark (1967) proved that this
additional value does not in fact exist, and soon afterwards it was observed that a gap
in a previous proof by Heegner (1952) could be filled without difficulty. It is conjec-
tured thatOdis a principal ideal domain for infinitely many positive values ofd,but
this remains unproved.
Much work has been done on determining for which quadratic number fields
Q(
√
d)the ring of integersOdis a Euclidean domain. Although we regard being
Euclidean more as a useful property than as an important concept, we report here the
results which have been obtained for their intrinsic interest.
The ringOdis said to benorm-Euclideanif it is Euclidean when one takesδ(a)to
be the absolute value of thenormofa. It has been shown thatOdis norm-Euclidean
for precisely the following values ofd:
d=− 11 ,− 7 ,− 3 ,− 2 ,− 1 , 2 , 3 , 5 , 6 , 7 , 11 , 13 , 17 , 19 , 21 , 29 , 33 , 37 , 41 , 57 , 73.It is known that, ford<0,Odis Euclidean only if it is norm-Euclidean. Comparing the
two lists, we see that ford=− 19 ,− 43 ,− 67 ,− 163 ,Odis a principal ideal domain,
but not a Euclidean domain. On the other hand it is also known that, ford= 69 ,Odis
Euclidean but not norm-Euclidean.
5 Congruences
The invention of a new notation often enables one to replace a long, involved argu-
ment by simple and mechanical algebraic operations. This is well illustrated by the
congruence notation.
Two i n t eg e r saandbare said to becongruent moduloa third integermifmdivides
a−b, and this is denoted bya≡bmodm. For example,
13 ≡4mod3, 13 ≡−7mod5, 19 ≡7mod4.The notation is a modification by Gauss of the notationa = bmodmused by
Legendre, as Gauss explicitly acknowledged (D.A.,§2). (Ifaandbare not congruent
modulom, we writea ≡ bmodm.) Congruence has, in fact, many properties in
common with equality:
(C1)a≡amodm for all a,m; (reflexive law)
(C2)if a≡bmodm,then b≡amodm; (symmetric law)
(C3)if a≡b and b≡cmodm,then a≡cmodm; (transitive law)
(C4)if a≡a′and b≡b′modm,then a+b≡a′+b′and
ab≡a′b′modm. (replacement laws)
The proofs of these properties are very simple. For anya,mwe havea−a= 0 =
m·0. Ifmdividesa−b, then it also dividesb−a=−(a−b).Ifmdivides botha−b
andb−c, then it also divides(a−b)+(b−c)=a−c. Finally, ifmdivides both
a−a′andb−b′, then it also divides(a−a′)+(b−b′)=(a+b)−(a′+b′)and
(a−a′)b+a′(b−b′)=ab−a′b′.
The properties(C1)–(C3)state that congruence modmis anequivalence relation.
Sincea=bimpliesa≡bmodm, it is a coarsening of the equivalence relation of