page 2  (20 pages) 1 3

Equation (1) is useful for theoretical purposes, but (3) is more convenient for computation as it leads to a simple algorithm for computing the coefficients of ?n(x) or evaluating ?n(x) at integer arguments using only integer arithmetic. If n is square-free the relations

?n(x) =

8
<

:

x ? 1; if n = 1;
1 + x + ? ? ? + xn?1; if n is prime;
?n=p(xp)=?n=p(x); if pjn, p prime, p < n;
(4)

give another convenient recursion for computing ?n(x).
Although ?n(x) is irreducible over Z (see for example [29]), ?n(x) may be reducible over certain quadratic fields. For example,

4?5(x) = (2x2 + x + 2)2 ? 5x2; (5)

so ?5(x) has factors x2 +
?1?p5
2

?
x + 1 whose coefficients are algebraic integers in Q[
p
5].

For odd square-free n > 1 the cyclotomic polynomial ?n(x) satisfies the identity

4?n(x) = A2n ? (?1)(n?1)=2nB2n: (6)

Gauss [12] proved (6) for odd prime n; the generalization to other odd square-free n is due to Dirichlet [11]. Related identities of Aurifeuille and Le Lasseur [2] are

?n((?1)(n?1)=2x) = C2n ? nxD2n (7)

for odd square-free n, and
?n=2(?x2) = C2n ? nxD2n (8)

for even square-free n > 2. For a proof, see Lucas [22] or Schinzel [26].

In (6{8), An(x); : : : ; Dn(x) are polynomials with integer coefficients, and without loss of generality we can assume that An(x)=2, Bn(x), Cn(x) and Dn(x) are monic. In Section 3 we show how the coefficients of An; : : : ; Dn can be computed by simple algorithms which require O(n2) arithmetic operations and work entirely over the integers.

In Section 1.1 we summarize our notation for future reference. Some numerical examples are given in Sections 1.2{1.3, and Newton's identities are discussed in Section 1.4. Then, in Section 2, we discuss the theoretical basis for the algorithms. The results for An and Bn are known (though perhaps forgotten) { they may be found in Dirichlet [11]. We present them in Section 2.2 for the sake of completeness and to aid the reader in understanding the results for Cn and Dn.

The algorithms are presented in Section 3. The algorithm (Algorithm D) for computing An and Bn is essentially due to Dirichlet [11], who illustrated it with some numerical examples but did not state it in general terms. The algorithm (Algorithm L) for computing Cn and Dn appears to be new. In Section 3.3 we comment briefly on Stevenhagen's algorithm [27] and compare it with Algorithm L.

Finally, in Section 4 we give some explicit formulas for An(x); : : : ; Dn(x). These may be regarded as generating functions if x is an indeterminate, or may be used to compute An(x); : : : ; Dn(x) for given argument x. In the special case x = 1 the results for An(1); Bn(1) reduce to known formulas involving the class number of the quadratic field Q[p?n].

One application of cyclotomic polynomials is to the factorization of integers of the form an ? bn: see for example [6, 7, 8, 9, 15, 16, 24, 26, 27]. If x = m2n for any integer m, then (7{8) are differences of squares, giving rational integer factors of xn ? 1. Examples may be found in Section 4.4. For the reader interested in integer factorization, our most significant results are Algorithm L of Section 3.2 and Theorem 3 of Section 4.4.