Modifications NOT made to the second printing of the book A Course in Computational Algebraic Number Theory by Henri Cohen (19940513 version)

Graduate Texts in Mathematics 138, Springer-Verlag, 1993, XXI + 534 pages.

ISBN 3-540-55640-0 Springer-Verlag Berlin Heidelberg New York

ISBN 0-387-55640-0 Springer-Verlag New York Berlin Heidelberg

p. 189 Addendum. Line -9, replace the 4 lines starting with “We can always assume” and ending with “(see Exercise 17).” by the following.

“We do however have the following corollary:

Corollary 4.7.6.5. Let R be an order in K containing θ, let ω_{1}, …,ω_{n} be the HNF basis of R with respect to θ, and let d_{1} = 1, d_{2}, …,d_{n} be the integers defined in the preceding corollary. Further, let M be an R-module of rank n over ℤ and let (A, d) be its HNF with respect to the basis ω_{1}, …,ω_{n}, where d is the denominator and A = (a_{i,j}) is an integral matrix in upper triangular

HNF. Then for every i and j with i ≤ j, a_{j,j} divides a_{i,j} and a_{j,j} divides \frac{d_{j}}{d_{i}} a_{i,i}. In other words,

the HNF basis of M has the form

α_{j} = \frac{z_{j}}{d} (ω_{j} + ∑_{1≤i<j} h_{i,j}ω_{i}) ,

where the z_{j} are positive integers such that z_{j} | \frac{d_{j}}{d_{i}} z_{i} for i < j and the h_{i,j} satisfy 0 ≤ h_{i,j} < z_{i}/z_{j}

for i < j. Furthermore, z_{1} is the smallest positive element of dM ∪ ℤ.

Proof. Let M_{R} be the HNF matrix of R on the powers of θ, and (B, d) be the HNF matrix of the module M on the powers of θ. It is clear that we have A = M_{R}^{−1}B, and the corollary follows immediately by expanding the matrix product and using Theorem 4.7.5 and Corollary 4.7.6. □”

p. 418-419 replace the whole proof “Proof. (D. Zagier) … the validity of the algorithm. □” by the following:

Proof. (D. Zagier) If no factors are found during step 1, this means that all the prime factors of N are greater than N^{1/3} hence N has at most two prime factors.

Assume first that N is prime. Then the test in step 3 can never succeed. Indeed, if a^{2}−4kN = b^{2} then N | a^{2} − b^{2} hence N | (a − b) or N | (a + b) so a + b ≥ N, but this is impossible since the given inequalities on k and a imply that a < 2N^{2/3} + 1 and b < N^{1/3} so N ≤ 13. An easy check shows that for 3 ≤ N ≤ 13, N prime the test in step 3 does not succeed (note that for N = 2, k = 1 and a = 3 it does).

Assume now that N is composite, so that N = pq with p and q not necessarily distinct primes. We may assume that p ≤ q, hence N^{1/3} < p ≤ q, or in other words 1 ≤ q/p < N^{1/3}. Consider the continued fraction expansion of q/p. The successive convergents u_{n}/v_{n} are such that u_{n} and v_{n} form an increasing sequence. Let n be the unique index such that u_{n}v_{n} < N^{1/3} < u_{n+1}v_{n+1} (since pq > N^{1/3} such an n exists), and set r = u_{n}, s = v_{n}, r′ = u_{n+1}, s′ = v_{n+1}. Then, using the elementary properties of continued fractions, we have

|\frac{q}{p} − \frac{r}{s}| ≤ |\frac{r′}{s′} − \frac{r}{s}| = \frac{1}{ss′} ,

Typeset by AMS-TEX

but also, since s/r and s′/r′ are successive convergents to p/q, we have

|\frac{p}{q} − \frac{s}{r}| ≤ |\frac{s′}{r′} − \frac{s}{r}| = \frac{1}{rr′} .

Thus we obtain |pr − qs| ≤ p/s′ from the first inequality, |pr − qs| ≤ q/r′ from the second, and taking the geometric mean this gives

|pr − qs| ≤ \sqrt{\frac{pq}{r′s′}} < N^{1/3} .

If we set k = rs and a = ps + qr, we have a^{2} − 4kN = (ps − qr)^{2}. The congruences for a are easily checked, and so we see that step 3 succeeds with these values, thus proving the validity of the algorithm. □”