Canad. J. Math. Vol. 56 (1), 2004 pp. 71–76

Euclidean Rings of Algebraic Integers
Malcolm Harper and M. Ram Murty
Abstract. Let K be a finite Galois extension of the field of rational numbers with unit rank greaterthan 3. We prove that the ring of integers of K is a Euclidean domain if and only if it is a principal ideal
domain. This was previously known under the assumption of the generalized Riemann hypothesis for
Dedekind zeta functions. We now prove this unconditionally.

1 Introduction
An integral domain R is said to be Euclidean if there exists a map φ : R \ {0} → Nsuch that given any a, b ∈ R, there exist q and r such that a = bq + r with either r = 0or φ(r) < φ(b). Any such ring is a principal ideal domain (PID).
If R is the ring of integers of an algebraic number field, then clearly a necessary
condition for R to be Euclidean is that R be a PID. That this condition is also sufficient whenever the quotient field of R is not an imaginary quadratic field is a remarkable prediction of the generalized Riemann hypothesis (GRH) and is a beautiful
theorem of Weinberger [W]. Such a result, together with its connection to a number
field version of the Artin primitive root conjecture was first signaled in a paper ofSamuel [S]. In that paper, Samuel discusses the situation with quadratic extensionsof Q . After reviewing a general criterion of Motzkin [M] for a ring to be Euclidean,
he applies it to the context of quadratic fields.
This criterion is easily described. Let A0 = {0} and define inductively An to be
the set of elements r of R having the property that every residue class modulo r has
a representative in A j for some j < n. Thus, A1 consistsSof the unit group of R.
∞
Motzkin’s criterion is that R is Euclidean if and only if R = n=0 An .
Motzkin used his criterion to prove that of the nine imaginary quadratic fields ofclass number one, only five of them are Euclidean and for these fields, the norm map
serves as the function φ. In contrast, Samuel’s work [S] made the exciting predictionthat any ring of integers of a real quadratic field of class number one is Euclidean, but
not necessarily for the absolute√ value of the norm map serving as φ. In particular,
Samuel conjectured that Z[ 14] is Euclidean this being the quadratic field of smallest
discriminant whose nature was unresolved.
We refer the reader to Lenstra’s paper [L] for both the historical developments
and applications of these ideas in the more general context of function fields overfinite fields where the GRH is known and the analog of Weinberger’s theorem can beproved unconditionally.
√In an earlier paper [H], the first author proved that Z[ 14] is Euclidean without
the use of the generalized Riemann hypothesis. More generally, he proved that if K is
Received by the editors April 19, 2002; revised August 15, 2002.
The second author’s research was partially supported by an NSERC grant.
AMS subject classification: 11R04, 11R27, 11R32, 11R42, 11N36.
c Canadian Mathematical Society 2004.

71

72

Malcolm Harper and M. Ram Murty
a real quadratic field and OK its ring of integers whose discriminant is less than 500,
then OK is Euclidean if and only if OK has class number one. In the same paper, healso determined all the cyclotomic fields whose ring of integers is a Euclidean domain.
In this paper, we generalize the work of Harper [H] to a larger context that includes the abelian case. Our methods originate in the papers of Gupta, K. Murty andR. Murty [GMM] where the first attempt was made to make Weinberger’s results unconditional using the earlier work [GM] on Artin’s primitive root conjecture. Theirwork studied the ring OK,S of S-integers where S was a finite set of places that included the infinite places and required |S| ≥ max(5, 2[K : Q ] − 3) to be applicable in
the Euclidean context. A novel idea was injected into the method by Clark and Murty[CM] in 1995. This idea allowed one to discover new Euclidean rings of integers oftotally√real Galois extensions K over Q with [K : Q ] ≥ 4. Thus, at that time, the caseof Z[ 14] was still elusive.
In [H], a variant of the Motzkin criterion was discovered, which when combinedwith the lower bound sieve results of previous works on the problem, along with aclever use of the large sieve inequality, finally led to the applicability of the method tothe quadratic field context.
The goal of this paper is to prove:
Theorem 1 Let K/Q be a finite Galois extension with unit rank r > 3. Then O K is
Euclidean if and only if OK is a PID.
As a corollary, we deduce:
Corollary Let K/Q be a finite Galois extension of degree > 8. Then O K is Euclidean if
and only if OK is a PID.
Indeed, if r1 and r2 denotes the number of real and complex embeddings of K
respectively, we have r > (r1 + 2r2 − 2)/2 = (n − 2)/2 so that r > 3 whenever n > 8
and r1 > 0. If r1 = 0, then r = r2 − 1 > 3 whenever n > 8.
The proof of this theorem involves many important ideas. In addition to theMotzkin criterion described above, the generalization of the Bombieri-Vinogradovtheorem to algebraic number fields as developed by K. Murty and R. Murty [MM]plays a vital role. Their generalization has two versions, one which is unconditional and another which assumes the Artin holomorphy conjecture for the Artin
L-functions that intervene. Undoubtedly, we feel that there is great scope for further improvements. In particular, it should be possible to sharpen the theorem toallow r = 3. This is possible in the abelian case thanks to a theorem of Bombieri,Friedlander and Iwaniec [BFI] extending the range of applicability of the BombieriVinogradov theorem beyond the usual limit of x 1/2 in the lower bound sieve method.
Such a result is not available in the non-abelian context and so our result stands withthe strict inequality at present. Still, by injecting ideas utilised in Theorem 2 (below),
especially the notion of admissible primes, one can hope to make further improvements. This we hope to develop in future research.
As is well-known, the Euclidean algorithm plays an important role in the study ofbounded generation of arithmetic groups. We state that one can apply our theorem
to this study, and refer the reader to the exposition of K. Murty [KM].

Euclidean Rings of Algebraic Integers

73

2 Variation of Motzkin’s Criterion
In [H], Harper discovered a variation of Motzkin’s criterion applicable to rings ofintegers of algebraic number fields. This can be described as follows.
First we define the notion of admissible sets of primes as described by Clark andMurty [CM]. Let K be an algebraic number field, OK its ring of integers. We supposethat OK is a PID. Let π1 , . . . , πs ∈ OK be distinct non-associate primes. We say{π1 , . . . , πs } is an admissible set of primes if for all β = π1a1 · · · πsas with ai nonnegative integers, every coprime residue class (mod β) can be represented by a unitof OK . As noted in [CM], to check if {π1 , . . . , πs } is admissible, it suffices to checkthat every coprime residue class (mod π12 · · · πs2 ) can be represented by a unit of OK .
Now let B0 be the monoid generated by the unit group and an admissible set ofprimes (which could be empty). For n ≥ 1, inductively define Bn as the set of allprimes π of OK such that every non-zero residue class modulo (π) has a representative in Bn−1 ∪ B0 . Thus, B1 is the set of primes π such that every residue class mod π
is represented by an element of B0 . The fundamental result in [H] is:
SProposition 1 Suppose OK is a PID. If all the primes of OK lie in ∞n=0 Bn , then OK isEuclidean.
A key innovation in the argument of Harper [H] was the following application ofthe large sieve inequality.
Proposition 2 Suppose that OK is a PID. Let Bn (x) denote the cardinality of the set ofelements in Bn whose norm is less than or equal to x. If
B1 (x) x,log2 xthen OK is Euclidean.
It is this last proposition that simplfies the earlier approaches to the study of Euclidean rings of algebraic integers. Indeed, in the proofs below we apply the lower
bound sieve to establish Proposition 2.

3 Preliminaries
We record in this section various theorems from the literature which will be neededin the proofs.
Proposition 3 ([MM]) Let K/Q be a finite Galois extension with group G. Let C be a
conjugacy class of G, and a, q be positive integers with 1 ≤ a < q, (a, q) = 1. Denoteby πC (x, q, a) the number of primes p ≤ x such that p ≡ a(mod q) with Artin symbol(p, K/Q ) ∈ C. There exist numbers δ(C, q, a) ≥ 0 such that for any  > 0 and A > 0,we haveXx,max max |πC (y, q, a) − δ(C, q, a)π(y)| (a,q)=1 y≤x(log x)Aq≤Q

α−with Q = x
where α ≤ min(2/|G|, 1/2) and the summation is over q such thatK ∩ Q (ζq ) = Q . (Here, π(y) denotes the number of primes p ≤ y.)74

Malcolm Harper and M. Ram Murty
This is the basic result of [MM]. However, as remarked in Section 7 of that paper,some improvements can be made (see, in particular Theorem 7.3 and Section 7.4).
Proposition 4 ([MM, p. 269]) With the same setting as in Proposition 3, let A be anyabelian subgroup of G with A∩C 6= φ. Let d = [G : A]. Then, we may take Q = x 1/η−in Proposition 3 with(d − 2 if d ≥ 4
η=2if d ≤ 4.
Moreover, we may replace d above by d ∗ whered∗ = min max[G : H]ω(1)Hω

where the minimum is taken over all subgroups H satisfying the two conditions••H ∩ C 6= φ andfor every irreducible character ω of H and any non-trivial Dirichlet character χ, theArtin L-series L(s, ω ⊗ χ) is entire.

The maximum above is over all irreducible characters of H. In particular, if Artin’s
holomorphy conjecture is true for K/Q , then we may take d ∗ = maxχ χ(1) where themaximum is over all irreducible characters of G.
Proposition 5 (Application of the Lower Bound Sieve) Let K/Q be a finite Galois
extension and sett = max{m : K ⊇ Q (ζm )}.
mLet η be as in Proposition 4 with C = 1. Then, the number of primes p ≤ x suchthat p splits completely in K and such that for every prime ` with `|(p − 1)/t we have
` > x1/2η− , isx.
log2 x
Proposition 6 (Gupta-Murty [GM]) Let K be an algebraic number field. Let M be a
monoid in OK and for p coprime to the elements of M, denote by fM (p) the order of M
mod p. If M contains r multiplicatively independent elements, then#{p : fM (p) ≤ Y }  Y (r+1)/r .

4 The Abelian Case
We begin with Lemma 4 of [H].
Proposition 7 Suppose OK is a PID and contains a set of s admissible primes. Let r be0
the rank of O×
K modulo torsion and define t = max{d : ζd 0 ∈ K}. If r + s ≥ 3 and if
there are a and k ∈ Z satisfying(1) gcd(a, k) = 1;(2) gcd(a − 1, k) = t; and(3) p ≡ a(mod k) implies there is a prime p of K with norm p,
then OK is Euclidean.

Euclidean Rings of Algebraic Integers

75

We will use this proposition to establish the following:
Theorem 2 Let K/Q be abelian of degree n with OK a PID that contains s admissible
primes. Let r be the rank of the unit group. If r + s ≥ 3, then OK is Euclidean.
Proof Let t be as in Proposition 7. We count the number of primes p ≤ x such thatp splits completely in K and p does not split completely in Q (ζ `t ) for `|t. Let k bethe conductor of K. Since K/Q is abelian, this means that there is a set S of residue
classes mod k such that p splits completely in K if and only if p ≡ a(mod k) witha ∈ S. Since Q (ζt ) is contained in K, we have a ≡ 1(mod t). We want to show that
there is an a in S satisfying the conditions of Proposition 7, namely gcd(a − 1, k) = t.
To do this, it suffices to show that there is a positive density of primes p which split
competely in K but not in Q (ζ`t ) for `|t for these primes will satisfy gcd(p −1, k) = t.
If we let K`t = K Q (ζ`t ), then the number of primes in our count isXµ(δ)π(Ktδ , x)

δ|twhere π(L, x) is the number of primes p ≤ x splitting completely in L. Since thedegree of Ktδ over Q is nδ as is easily checked, we have by the Chebotarev density
theorem, that the quantity in question is∼X
δ|tµ(δ)π(x)π(x) φ(t)=,nδntwhich is a positive proportion. This completes the proof.

5 Proof of the Main Theorem
We want to use Proposition 2 to show that OK is Euclidean. Let B1 (x) count the num×
ber of primes π with norm less than x for which we have O×
K (mod π) = (OK /π) .
It suffices to show thatx.
B1 (x) log2 x
By Proposition 5, the number of primes π which split completely in K with p =NK/Q (π) ≤ x having the property that any prime ` dividing p − 1 is either greaterthan x1/2η− or a divisor of t, (where t, η are defined in Proposition 5) isx.
log2 xFor p sufficiently large, we already know that t divides the order of the image of×O×K mod π since the group of roots of unity injects into (O K /π) . By virtue of theconstraint on p guaranteed by Proposition 5, no prime dividing t can divide theindex of the image. Thus, the only possible prime divisors of the index are greater

76

Malcolm Harper and M. Ram Murty
than x1/2η− which means that if the index is not 1, then the size of the image is lessthan x1−1/2η+ . By Proposition 6, the number of such primes isO(x(1−1/2η+)(1+1/r) ) = o(x/ log2 x)
whenever η < (r + 1)/2. We apply Proposition 5. We determine η of Proposition 4 asfollows. Let G = Gal(K/Q ) and let A be an abelian subgroup of G. Set d = [G : A].
If d ≤ 4, we can take η = 2 so we need r > 3. If d ≥ 4, we can take η = d − 2, andwe need d − 2 < (r + 1)/2 which means we need to ensure r > 2d − 5. This is thecase if G has an abelian subgroup of order e ≥ 4, sincer = r 1 + r2 − 1 ≥r1 + 2r2 − 2n−22n=>− 5 = 2d − 5.
22eThus, we may assume every prime divisor of |G| = n is ≤ 3. Hence, n = 2 a 3b . Ifb ≥ 2, G has a subgroup of order 9 and again by the above argument we are done.
If a ≥ 2, we are also done. The only case left is if n divides 6. As the abelian casewas dealt with in the previous section, the only case to treat is the non-abelian case ofn = 6. But in this case, we have Artin’s conjecture on the holomorphy of non-abelianL-series, so that we may take η = 2 in Proposition 4. Thus, r > 3 is allowed and theproof is complete.
Acknowledgments The authors would like to thank the referee for helpful comments and suggestions.

References[BFI][CM]
[GM]
[GMM]
[H]
[L]
[M]
[KM]
[MM]
[S]
[W]

E. Bombieri, J. Friedlander and H. Iwaniec, Primes in arithmetic progressions to large moduli.
Acta Math. 156(1986), 203–251.
D. Clark and M. Ram Murty, The Euclidean algorithm for Galois extensions of Q . J. Reine
Angew. Math. 459(1995), 151–162.
R. Gupta and M. Ram Murty, A remark on Artin’s conjecture. Invent. Math. 78(1984), 127–130.
R. Gupta, M. Ram Murty and V. Kumar Murty, The Euclidean algorithm for S-integers. In:
Number Theory√ (eds. H. Kisilevsky and J. Labute), CMS Conf. Proc. 7(1987), 189–201.
M. Harper, Z[ 14] is Euclidean. Canad. J. Math. 56(2004), 55–70.
H. Lenstra, Euclidean number fields, I. Math. Intelligencer 2(1979), 6–15.
Th. Motzkin, The Euclidean algorithm. Bull. Amer. Math. Soc. 55(1949), 1142–1146.
V. Kumar Murty, Bounded and Finite Generation of Arithmetic Groups. In: Number Theory(ed. K. Dilcher), CMS Conf. Proc. 15(1995), 249–261.
M. Ram Murty and V. Kumar Murty, A variant of the Bombieri-Vinogradov theorem. In:
Number Theory (eds. H. Kisilevsky and J. Labute), CMS Conf. Proc. 7(1987), 243–272.
P. Samuel, About Euclidean Rings. J. Algebra 19(1971), 282–301.
P. Weinberger, On Euclidean rings of algebraic integers. In: Analytic Number Theory (St. Louis,1972), Proc. Sympos. Pure Math. 24(1973), 321–332.

Champlain College
MontrealCanada
email: malcolmharper@sympatico.ca

Department of Mathematics
Queen’s University
Kingston, Ontario
K7L 3N6
email: murty@mast.queensu.ca