% To be compiled with AmsTeX 2.0 or later
\magnification=\magstephalf
% \nologo
\font\sans=cmss10
\def\ltextindent#1{\hbox to \hangindent{#1\hss}\ignorespaces}
\def\litem{\par\noindent\dimen0=\parindent%
\advance\dimen0 by-4pt
\hangindent=\dimen0\ltextindent}
\def\llitem{\par\noindent
\hangindent=\parindent\ltextindent}
\def\stno#1{\litem{\sans #1}}
\def\exno#1{\llitem{\rm #1}}
\def\t{\theta}
\def\p{\goth p}
\def\om{\omega}
\def\eps{\varepsilon}
\def\Z{\Bbb Z}
\def\Q{\Bbb Q}
\def\F{\Bbb F}
\def\fp{\qed}
\def\bb{\bold b}
\def\N{\operatorname{\Cal N}}
\def\ov#1{\overline{\vphantom{T}#1}}
\def\leg#1#2{\fracwithdelims(){#1}{#2}}
\centerline{\bf Errata et Addenda to the Book}
\smallskip
\centerline{\bf A Course in Computational Algebraic Number Theory}
\smallskip
\centerline{by \bf Henri Cohen}
\smallskip
\centerline{(19940513 version)}
\medskip
{\obeylines
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
\bigskip
p. VII\quad line 1 add ``Andrew Odlyzko,'' after ``Nicolas,''
p. X\quad line -7, instead of ``algorithms'' read ``an algorithm''
p. XIII\quad e-mail address, remove ``{\tt ecole.}''
p. XIII\quad end, add the following:
``In addition, a regularly updated errata file is available by anonymous ftp from
{\tt megrez.ceremab.u-bordeaux.fr (147.210.16.17)}, directory {\tt pub/cohenbook}.''
p. XX\quad 8.4., instead of ``Lehmann'' read ``Lehman''
p. 1\quad line -13, instead of ``is that it is'' read ``that it is''
p. 2\quad line -4, instead of ``easily'' read ``easy''
p. 2\quad line -2 replace ``Cayley/Magma'' by ``Magma'' and insert after ``Macsyma''
p. 3\quad line 16, instead of ``not.'' read ``not).''
p. 4\quad line -2, instead of ``$a*b$'' read ``$a\cdot b$''
p. 10\quad lines 1 and 2, instead of ``$O(\ln m\ln|n|)$ instead of $O(\ln^2m\ln\ln|n|)$ for'' read ``in average up to $1.5$ times faster than''
p. 10\quad step 1 of Algorithm 1.2.4, instead of ``$z\gets g$ and $f\gets e$.'' read ``$z\gets g$. Finally, set $f\gets e$.''
p. 13\quad step 1 of Algorithm 1.3.3, instead of ``simple precision'' read ``single precision''
p. 17\quad step 2 of Algorithm 1.3.7, instead of ``simple precision'' read ``single precision''
p. 20\quad line -4, instead of ``$x_i=$'' read ``$x_i$''
p. 22\quad line 13, instead of ``$\dots]$.'' read ``$\dots]$).''
p. 22\quad replace step 3 of Algorithm 1.3.13 by the following:
}
\smallskip
{\sans\stno{``3.}\quad [Output quotient] Set $a_i\gets q$ and output $a_i$,
then set $i\gets i+1$, $a\gets b$, $b\gets r$, $a'\gets b'$ and $b'\gets r'$.
If $b$ and $b'$ are non-zero, go to step 2. If $b=b'=0$, terminate the
algorithm. Finally, if $b=0$ set $q\gets\infty$ and
$q'\gets\lfloor a'/b'\rfloor$ while if $b'=0$ set $q\gets\lfloor a/b\rfloor$
and $q'\gets\infty$.''}
\smallskip
{\obeylines
p. 37\quad line 14, instead of ``custom'' read ``special-purpose''
p. 37\quad steps 1 and 3, instead of ``above'' read ``below''
p. 37\quad replace step 2 by the following:
}
\smallskip
{\sans\stno{``2.}\quad [Small degree?] If $\deg(A)=0$, terminate the
algorithm.If $\deg(A)=1$, and $A(X)=a_1X+a_0$, output $-a_0/a_1$ and
terminate the algorithm.
If $\deg(A)=2$ and $A(X)=a_2X^2+a_1X+a_0$, set $d\gets a_1^2-4a_0a_2$, compute
$e\gets\sqrt d$ using Algorithm 1.5.1, output $(-a_1+e)/(2a_2)$ and
$(-a_1-e)/(2a_2)$, and terminate the algorithm. (Note that $e$ will exist.)''}
\smallskip
{\obeylines
p. 41\quad line 13 to line -1, replace completely by the following:
}
\smallskip
``The idea is to use the following proposition.
\proclaim{\bf Proposition 1.7.4} Let $n=p^k$ be a prime power. Then
\roster\item For any $a$ we have $p\mid (a^n-a,n)$.
\item If $k\ge2$ and $p>2$, let $a$ be a witness to the compositeness of $n$
given by the Rabin-Miller test 8.2.2, i.e. such that $(a,n)=1$, and if
$n-1=2^tq$ with $q$ odd, then $a^q\not\equiv1\pmod n$ and for all $e$ such
that $0\le e\le t-1$ then $a^{2^eq}\not\equiv-1\pmod n$. Then $(a^n-a,n)$ is a
non-trivial divisor of $n$ (i.e. is different from 1 and $n$).\endroster
\endproclaim
{\it Proof.\/} By Fermat's theorem, we have $a^n\equiv a\pmod p$, hence (1) is
clear. Let us prove (2). Let $a$ be a witness to the compositeness of $n$ as
defined above. By (1), we already know that $(a^n-a,n)>1$. Assume
that $(a^n-a,n)=n$, i.e. that $a^n\equiv a\pmod n$. Since $(a,n)=1$ this is
equivalent to $a^{n-1}\equiv1\pmod n$, i.e. $a^{2^tq}\equiv1\pmod n$. Let
$f$ be the smallest non-negative integer such that $a^{2^fq}\equiv1\pmod n$.
Thus $f$ exists and $f\le t$. If we had $f=0$, this would contradict the
definition of a witness ($a^q\not\equiv1\pmod n$). So $f>0$. But then
we can write $$p^k\mid (a^{2^{f-1}q}-1)(a^{2^{f-1}q}+1)$$and since $p$ is
an odd prime, this implies that $p^k$ divides one of the two factors. But
$p^k\mid (a^{2^{f-1}q}-1)$ contradicts the minimality of $f$, and
$p^k\mid (a^{2^{f-1}q}+1)$ contradicts the fact that $a$ is a witness
(we cannot have $a^{2^eq}\equiv-1\pmod n$ for $e1$, this algorithm tests whether or not $n$ is of the form $p^k$
with $p$ prime, and if it is, outputs the prime $p$.\smallskip
\stno{1.}\quad [Case $n$ even] If $n$ is even, set $p\gets2$ and go to
step 4. Otherwise, set $q\gets n$.\smallskip
\stno{2.}\quad [Apply Rabin-Miller] By using Algorithm 8.2.2 show that either
$q$ is a probable prime or exhibit a witness $a$ to the compositeness of $q$.
If $q$ is a probable prime, set $p\gets q$ and go to step 4.\smallskip
\stno{3.}\quad [Compute GCD] Set $d\gets(a^q-a,q)$. If $d=1$ or $d=q$, then
$n$ is not a prime power and terminate the algorithm. Otherwise set
$q\gets d$ and go to step 2.\smallskip
\stno{4.}\quad [Final test] (Here $p$ is a divisor of $n$ which is almost
certainly prime.) Using a primality test (see Chapters 8 and 9) prove that
$p$ is prime. If it is not (an exceedingly rare occurence), set $q\gets p$
and go to step 2. Otherwise, by dividing $n$ by $p$ repeatedly, check whether
$n$ is a power of $p$ or not. If it is not, $n$ is not a prime power, otherwise
output $p$. Terminate the algorithm.}\endproclaim
\medskip
We have been a little sloppy in this algorithm. For example in step 4,
instead of repeatedly dividing by $p$ we could use a binary
search analogous to the binary powering algorithm. We leave this as an
exercise for the reader (Exercise 4).''
\smallskip
{\obeylines
p. 48\quad line 1 of step 5 of Algorithm 2.2.1, instead of ``$k>l$'' read ``$k>j$''
p. 51\quad replace the last two lines of Proposition 2.2.5 by the following:
``Finally, let $c_n=a_{n,n}^{(n-1)}$. Then all the divisions by $c_{k-1}$ are exact; we have $\det(M_k)=c_k^{n-k-1}\det(M_0)$, and in particular $\det(M_0)=c_n$.''
p. 51\quad line -15, instead of ``$k+1\times k+1$'' read ``$(k+1)\times(k+1)$''
p. 51\quad line -4 instead of ``$sM_{n,n}$'' read ``$sm_{n,n}$''
p. 55\quad line 20, instead of ``$p_m(X)=...$'' read ``$p_m(X)\gets...$''
p. 59\quad line -2 instead of ``a $m\times r$'' read ``an $m\times r$''
p. 59\quad line -2 instead of ``$r\le n\le m$'' read ``$n\le m$''
p. 59\quad line -1 instead of ``a $n\times r$'' read ``an $n\times r$''
p. 60\quad line 3, instead of ``$X'_i$'' read ``$M'_i$, $X'_i$'' and instead of ``$X$)'' read ``$M$, $X$)''
p. 61\quad lines 5 to 8, replace step 4 by the following:
}
\smallskip
{\sans\stno{``4.}\quad [Modify basis and eliminate] Set $B_t\gets B_s$ (if
$t\neq s$), then set $B_s\gets M_s$. Then for $j=s+1$,\dots,$k$, do as follows.
Exchange $m_{s,j}$ and $m_{t,j}$ (if $t\neq s$). Set $m_{s,j}\gets dm_{s,j}$.
Then for all $i\neq s$ and $i\neq t$, set
$m_{i,j}\gets m_{i,j}-m_{i,s}m_{s,j}$. Finally, go to step 2.''}
\smallskip
{\obeylines
p. 61\quad line 2 of Algorithm 2.3.7, instead of ``column'' read ``columns''
p. 71\quad lines -6 to -1, replace step 4 by the following:
}
\smallskip
{\sans\stno{``4.}\quad [Next row] Using Euclid's extended algorithm, find
$(u,v,d)$ such that $ua_{i,k}+vR=d=\gcd(a_{i,k},R)$. Set
$W_i\gets uA_k\bmod R$ (here taken in the interval $[0,R-1]$). If
$w_{i,i}=0$ set $w_{i,i}\gets R$. For $j=i+1,\dots,m$ set
$q\gets\lfloor w_{i,j}/w_{i,i}\rfloor$ and $W_j\gets W_j-qW_i$.
If $i=1$, output the matrix $W=(w_{i,j})_{1\le i,j\le m}$
and terminate the algorithm. Otherwise, set $R\gets R/d$, $i\gets i-1$,
$k\gets k-1$, $j\gets k$, and if $a_{i,k}=0$ set $a_{i,k}\gets R$.
Go to step 2.''}
\smallskip
{\obeylines
p. 73\quad line 2 of step 4 of Algorithm 2.4.10, instead of ``step 6'' read ``step 5''
p. 79\quad line 1, instead of ``for all'' read ``for all non-zero''
p. 82\quad line 4, instead of ``exists'' read ``exist''
p. 87\quad line 6, instead of ``set'', read ``set (in this order)''
p. 87\quad line 6, just before ``$B_k\gets B_{k-1}B_k/B$'' insert ``$\bb\gets\bb_{k-1}^*$, $\bb_{k-1}^*\gets\bb_k^*+\mu\bb$,
$\bb_k^*\gets -\mu_{k,k-1}\bb_k^*+(B_k/B)\bb$, ''
p. 88\quad line 11, instead of ``Gram-Schmidt'' read ``Gram''
p. 88\quad line 13, instead of ``so that statements ... removed'' read ``and the updating of the vectors $\bb_i$ done in Sub-algorithms RED and SWAP must be done directly on the Gram matrix''
p. 89\quad line 13, instead of ``to be LLL'' read ``from being LLL''
p. 93\quad line 3 of Algorithm REDI, after ``$H_k\gets H_k-qH_l$,'' insert `` $\bb_k\gets \bb_k-q\bb_l$,''
p. 93\quad line 1 of Algorithm SWAPI, after ``$H_k$ and $H_{k-1}$,'' insert `` exchange $\bb_k$ and $\bb_{k-1}$,''
p. 93\quad line 4 of Algorithm SWAPI, instead of ``$t+\lambda\lambda_{i,k}/B$'' read ``$(Bt+\lambda\lambda_{i,k})/d_k$''
p. 94\quad line 2 of step 2, instead of ``$\mu_{k,j}=0$'' read ``$\mu_{k,j}\gets0$''
p. 94\quad just before step 1, instead of ``$\bold r\cdot\bb_i=0$ for all $i$'' read ``$\sum_{1\le i\le n}r_i\bb_i=0$''
p. 94\quad line -5, after ``echange $B_k$ and $B_{k-1}$'', insert ``, exchange $\bb_k^*$ and $\bb_{k-1}^*$''
p. 94\quad line -3, after ``$B_{k-1}\gets B$'', insert ``, $\bb_{k-1}^*\gets\mu\bb_{k-1}^*$''
p. 94\quad line -1, after ``$\mu_{k,k-1}\gets\mu t$'' insert ``$\bb\gets\bb_{k-1}^*$, $\bb_{k-1}^*\gets\bb_k^*+\mu\bb$, $\bb_k^*\gets -\mu_{k,k-1}\bb_k^*+(B_k/B)\bb$, ''
p. 95\quad line 10, instead of ``it itself'' read ``is itself''
p. 101\quad line 7, instead of ``$n+1\times n$'' read ``$(n+1)\times n$''
p. 106\quad Exercise 28, instead of ``In'' read ``in''
p. 106\quad line -3, instead of ``accordingly'' read ``accordingly.''
p. 107\quad line 2, instead of ``Chapter 3.)'' read ``Chapter 3).''
p. 108\quad line 3, instead of ``[Knu1]'' read ``[Knu2]''
p. 110\quad last line of Algorithm 3.1.1, instead of ``got to'' read ``go to''
p. 114\quad line -4, instead of ``$s=\prod_p p^{v_p(s)}$'' read ``$s=u\prod_p p^{v_p(s)}$''
p. 114\quad line -3, instead of ``where'' read ``where $u$ is a unit,''
p. 117\quad lines 12 to 16, replace the two sentences starting with ``We can still divide'' and ending with ``algorithm.'' by
}
\smallskip
``We could still try to divide $A$ and $B$ by their content from time to time
(say every 10 iterations), but this would usually be a very bad idea (see
Exercise 4).''
\smallskip
{\obeylines
p. 117\quad end of step 1, instead of ``, $h\gets1$ and $c\gets 0$.'' read `` and $h\gets1$.
p. 117\quad replace completely step 3 by
}
\smallskip
{\sans\stno{``3.}\quad [Reduce remainder] Set $A\gets B$, $B\gets R/(gh^\delta)$,
$g\gets\ell(A)$, $h\gets h^{1-\delta}g^\delta$ and go to step 2.
(Note that all the divisions which may occur in this step give
a result in the ring $\Cal R$.)}''
\smallskip
{\obeylines
p. 120\quad line 13, instead of ``$\ell(A)^{2m-2}$'' read ``$\ell(A)^{m-1+\deg(A')}$''
p. 120\quad line -8, instead of ``$a^{2m-1}$'' read ``$a^{m+\deg(A')}$''
p. 120\quad line -7, instead of ``proposition.'' read ``proposition. Note that we have $\deg(A')=m-1$ except when the characteristic of $R$ is non-zero and divides $m$.''
p. 121\quad lines 1 to 3, suppress the two sentences ``Contrary to ... Exercise 4).''
p. 124\quad lines -10 and -9, replace the sentence ``For $k\ge2$,...$T_k=T_{k-1}/V_k$.'' by
``For $k\ge1$, set $V_{k+1}=(T_k,V_k)$ if $p\nmid k$, $V_{k+1}=V_k$ if $p\mid k$, and $T_{k+1}=T_k/V_{k+1}$.''
p. 125\quad line 1, instead of ``$A=\in\F_p[X]$'' read ``$A\in\F_p[X]$''
p. 125\quad line -6, instead of `` and go to step 2'' read ``. Go to step 2.''
p. 126\quad line 3, instead of ``(see Knu2])'' read ``(see [Knu2])''
p. 128\quad lines 1 and 2 of step 2, instead of ``Set $C\gets T$ \dots $C\gets C+D$.'' read ``Set $C\gets T$ and then repeat $d-1$ times $C\gets T+C^2\bmod A$.''
p. 128\quad line -21 to -19, instead of ``Knuth gives \dots power of 2'' read ``Knuth gives $C\gets C+C^2\bmod A$, but this should be instead, as above, $C\gets T+C^2\bmod A$''
p. 131\quad line 3 of Step 1, add ``$\pmod{A(X)}$'' at the end of the formula
p. 132\quad line 2, instead of ``degree $n$,'' read ``degree $n$ (with $p\ge3$),''
p. 132\quad line 2 of step 4 of Algorithm 3.4.11, instead of ``$\deg(D)>1$'' read ``$\deg(D)>0$''
p. 132\quad line 3 of step 4 of Algorithm 3.4.11, instead of ``computations'' read ``computation''
p. 132\quad end of Algorithm 3.4.11, put the ``3'' on the same line as ``go to step'' (this is not a misprint, but an important \TeX nical change)
p. 135\quad line -15, instead of ``any factor of $A$'' read ``up to sign, any factor of $A$''
p. 136\quad line -9, instead of ``$S\equiv(VD\bmod A_e)\pmod p$ and $T\equiv(UD\bmod B_e)\pmod p$'' read ``$S\equiv VD+WA_e\pmod p$ and $T\equiv UD-WB_e\pmod p$ for some polynomial $W$''
p. 137\quad line -12, instead of ``find'' read ``finds''
p. 143\quad line 1, instead of ``$n$'' read ``$m$''
p. 143\quad line 4, instead of ``$1\le j\le n$'' read ``$1\le j\le m$''
p. 143\quad line 14, instead of ``$N_i^n$'' read ``$N_i^m$''
p. 143\quad line 14, instead of ``$N_i^{n'}$'' read ``$N_i^{m'}$''
p. 143\quad line 15, instead of ``$n'\le n$'' read ``$m'\le m$''
p. 147\quad replace Exercise 4 by the following.
}
\smallskip
\exno{``4.}\quad Modify Algorithm 3.3.1 so that $A$ and $B$ are divided by
their respective contents every 10 iterations. Experiment and convince
yourself that this modification leads to polynomials $A$ and $B$ having much
larger coefficients later on in the Algorithm, hence that this is a bad idea.''
\smallskip
{\obeylines
p. 147\quad Exercise 5, instead of ``$r\times(A,B)$'' read ``$r\cdot(A,B)$''
p. 154\quad line 7, instead of ``More generally, for'' read ``For''
p. 155\quad line 17, instead of ``a polynomial'' read ``an irreducible polynomial''
p. 162\quad line -13, instead of ``$Z$'' read ``$\Z$''
p. 163\quad line -9, instead of ``independent'' read ``dependent''
p. 185\quad middle, instead of ``$N_{K/\Bbb Q}(x)$'' read ``${\Cal N}_{K/\Bbb Q}(x)$''
p. 189\quad {\bf Addendum.} Line -9, replace the 4 lines starting with ``We can always assume'' and ending with ``(see Exercise 17).'' by the following.
}
\smallskip
``We do however have the following corollary:
\proclaim{\bf Corollary 4.7.6.5} Let $R$ be an order in $K$
containing $\t$, let $\om_1$,\dots,$\om_n$ be the HNF basis of $R$
with respect to $\t$, and let $d_1=1$, $d_2$,\dots,$d_n$ be the
integers defined in the preceding corollary.
Further, let $M$ be an $R$-module of rank $n$
over $\Z$ and let $(A,d)$ be its HNF with respect to the basis
$\om_1$,\dots,$\om_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\le j$, $a_{j,j}$ divides $a_{i,j}$ and
$a_{j,j}$ divides $\dfrac{d_j}{d_i}a_{i,i}$. In other words, the HNF
basis of $M$ has the form
$$\alpha_j=\frac{z_j}d\left(\om_j+\sum_{1\le i19$'' read ``$p>457$''
p. 397\quad line 2 of Algorithm 7.4.12 instead of ``$p\ge 13$'' read ``$p>457$''
p. 398\quad line 14, instead of ``$100$, say'' read ``$457$. Note that one can prove that $457$ is best possible, but it is easy to modify slightly the algorithm so that it works for much lower values of $p$.''
p. 398\quad line -2 and -1, replace the last sentence by ``Using recent new ideas of Elkies, Atkin has been able to deal with a 200-digit prime. Finally, combining this with an idea of Couveignes and Morain, Morain has dealt with a 250-digit prime.''
p. 400\quad line -1, instead of ``$t1$'' read ``$t_1$''
p. 401\quad line 1, instead of ``$r_1*a_1$'' read ``$r_1a_1$''
p. 401\quad line 3 of step 15, instead of ``goto step 1'' read ``goto step 2''
p. 408\quad line 10, instead of ``{\sans , $a\gets b$, and if $a\le1$, set $a\gets1$ and go to step 4.}'' read ``{\sans and $a\gets\max(b,1)$.}''
p. 409\quad Exercise 1, replace the first sentence by ``Given $c_4$ and $c_6$ computed by Formulas (7.1), we would like to recover the $b_i$ and $a_i$, where we assume that the $a_i$ are in $\Z$.''
p. 415\quad line -9, instead of ``possible'' read ``usually possible''
p. 415\quad line -8, instead of ``finite set'' read ``reasonably small finite set''
p. 418\quad lines 8, 16, 19 and -6, instead of ``Lehmann'' read ``Lehman''
(the last three corrections are not necessary if the big change below is made)
p. 418\quad line -8, instead of ``{\it (*)\/}'' read ``{\it $(*)$\/}''
(not necessary if the big change below is made)
p. 418\quad {\bf Addendum.} Line 14 to the end of Section 8.4, replace completely by:
}
\smallskip
``Although several methods were introduced to improve trial division (which is,
we recall, a $O(N^{1/2+\epsilon})$ algorithm), the first method which has
a running time which could be proved to be substantially lower was introduced
by Lehman (see [Leh1]). Its execution time is at worst
$O(N^{1/3+\epsilon})$, and it is indeed faster than trial division already
for reasonably small values of $N$. The algorithm is as follows.
\smallskip
\proclaim\nofrills{\bf Algorithm 8.4.1}{\rm\ (Lehman). }{\sans Given an integer
$N\ge3$, this algorithm finds a non-trivial factor of $N$ if $N$ is
not prime, or shows that $N$ is prime.\smallskip
\stno{1.}\quad [Trial division] Set $B\gets\lfloor N^{1/3}\rfloor$. Trial divide
$N$ up to the bound $B$ using Algorithm 8.1.1. If any non-trivial factor is
found, output it and terminate the algorithm. Otherwise set $k\gets0$.
\smallskip
\stno{2.}\quad [Loop on $k$] Set $k\gets k+1$. If $k>B$, output the fact that $N$
is prime and terminate the algorithm. Otherwise, set $r=1$ and $m=2$ if $k$
is even, $r=k+N$ and $m=4$ if $k$ is odd.\smallskip
\stno{3.}\quad [Loop on $a$] For all integers $a$ such that $4kN\le a^2\le 4kN+B^2$
and $a\equiv r\pmod m$ do as follows. Set $c\gets a^2-4kN$. Using Algorithm
1.7.3, test whether $c$ is a square. If it is, let $c=b^2$, output
$\gcd(a+b,N)$ (which will be a non-trivial divisor of $N$) and terminate the
algorithm. Otherwise, use the next value of $a$ if any. If all possible
values of $a$ have been tested, go to step 2.}\endproclaim
\smallskip
{\it 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\mid a^2-b^2$ hence $N\mid (a-b)$ or
$N\mid(a+b)$ so $a+b\ge N$, but this is impossible since the given inequalities
on $k$ and $a$ imply that $a<2N^{2/3}+1$ and $bN^{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
$$\left|\dfrac qp-\dfrac rs\right|\le\left|\dfrac{r'}{s'}-\dfrac rs\right|=
\dfrac{1}{ss'}\enspace,$$but also, since $s/r$ and $s'/r'$ are successive
convergents to $p/q$, we have
$$\left|\dfrac pq-\dfrac sr\right|\le\left|\dfrac{s'}{r'}-\dfrac sr\right|=
\dfrac{1}{rr'}\enspace.$$
Thus we obtain $|pr-qs|\le p/s'$ from the first inequality, $|pr-qs|\le q/r'$
from the second, and taking the geometric mean this gives
$$|pr-qs|\le\sqrt{\dfrac{pq}{r's'}}n^{1/3}$'' read ``$s>N^{1/3}$''
p. 461\quad line 5, instead of ``i.e'' read ``i.e.''
p. 462\quad line 3 of step 7, instead of ``i.e'' read ``i.e.''
p. 463\quad line -13, instead of ``Miller'' read ``Elkies''
p. 467\quad line -2, instead of ``$p$ is prime'' read ``$p$ is an odd prime''
p. 468\quad {\bf Addendum.} Add the following exercises:
}
\smallskip
\exno{``7.}\quad Let $\chi$ be a character modulo $q$, where $q$ is not
necessarily prime. We will say that $\chi$ is {\it primitive\/} if for all
divisors $d$ of $q$ such that $d1$. Show that there exists a $u\in(\Z/q\Z)^*$ such that $au=d$. Deduce
from this that $\psi(a)=0$, and hence that the formula
$\psi(a)=\ov{\chi}(a)\tau(\chi)$ is still valid.\smallskip
\exno{8.}\quad Let $\chi$ be a primitive character modulo $q$, as defined
in the preceding exercise, and set $S(x)=\sum_{n\le x}\chi(n)$.
\newline\indent a) Using the preceding exercise, give an explicit formula for
$\tau(\chi)S(x)$.
\newline\indent b) Deduce that
$$\sqrt{q}\,|S(x)|\le\sum_{1\le m