124 II Divisibility
refinement theorem and the Jordan–H ̈older theorem may be viewed as generalizations
of Propositions 6 and 7. These theorems are stated and proved in Chapter I,§3of
Lang [23]. The fundamental theorem of arithmetic (Proposition 7) is usually attributed
to Gauss (D.A.,§16). However, it is really contained in Euclid’sElements(Book VII,
Proposition 31 and Book IX, Proposition 14), except for the appropriate terminology.
Perhaps this is why Euler and his contemporaries simply assumed it without proof.
Generalizations of the fundamental theorem of arithmetic to other algebraic struc-
tures are discussed in Chap. 2 of Jacobson [21]. For factorial domains, see Samuel [39].
Our discussion of the fundamental theorem did not deal with the practical problems
of deciding if a given integer is prime or composite and, in the latter case, of obtaining
its factorization into primes. Evidently if the integerais composite, its least prime
factorpsatisfiesp^2 ≤a. In former days one used this observation in conjunction with
tables, such as [24], [25], [26]. With new methods and supercomputers, the primal-
ity of integers with hundreds of digits can now be determined without difficulty. The
progress in this area may be traced through the survey articles [48], [7] and [27]. Fac-
torization remains a more difficult problem, and this difficulty has found an important
application inpublic-key cryptography;seeRivestet al.[37].
For Proposition 12, cf. Hillman and Hoggatt[17]. A proof that the ring of all al-
gebraic integers is a B ́ezout domain is given on p. 86 of Mann [31]. The ring of all
functions which are holomorphic in a given region was shown to be a B ́ezout domain
by Wedderburn (1915); see Narasimhan [32].
For Gauss’s version of Proposition 17, seeD.A.,§42. It is natural to ask if Corol-
lary 18 remains valid if the polynomial ringR[t] is replaced by the ringR[[t]] of
formal power series. The ringK[[t 1 ,...,tm]] of all formal power series in finitely
many indeterminates with coefficients from an arbitrary fieldKis indeed a factorial
domain. However, ifRis a factorial domain, the integral domainR[[t]] of all formal
power series intwith coefficients fromRneed not be factorial. For an example in
whichRis actually a complete local ring, see Salmon [38].
For generalizations of Eisenstein’s irreducibility criterion (Proposition 19), see
Gao [12]. Proposition 21 is proved in Rhai [36]. Euclidean domains are studied further
in Samuel [40]. Quadratic fieldsQ(
√
d)whose ring of integersOdis Euclidean are
discussed in Clark [3], Dubois and Steger [8] and Eggletonet al.[9].
Congruences are discussed in all the books on number theory cited above. In con-
nection with Lemma 32 we mention a resultof Frobenius (1895). Frobenius proved
that ifGis a finite group of ordernand ifdis a positive divisor ofn, then the number
of elements ofGwhose order dividesdis a multiple ofd. He conjectured that if the
number is exactlyd, then these elements form a (normal) subgroup ofG. The conjec-
ture can be reduced to the case whereGis simple, since a counterexample of minimal
order must be a noncyclic simple group. By appealing to the recent classification of all
finite simple groups (see Chapter V,§7), the proof of the conjecture was completed by
Iiyori and Yamaki [20].
There is a table of primitive roots on pp. 52–56 of Hua [18]. For more extensive
tables, see Western and Miller [47].
It is easily seen that an even square is never a primitive root, that an odd square
(including 1) is a primitive root only for the primep=2, and that−1 is a primitive
root only for the primesp= 2 ,3. Artin (1927) conjectured that if the integerais not