A Course in Computational Number Theory

David Bressoud & Stan Wagon

• page viii,
page number for A Dozen Prime Mysteries should be 142
• page 5, exercise 1.6 (b)

"F_m = A^m" should instead say that "F_m is the off-diagonal entry in A^m".

The last sentence should end with "...any power of B." rather than "...any power of b."

• page 10, line -4

The command should be “Table[ContinuantQ[Take[qVals,i]],{i,-5,0}]”

• page 14, lines 10-12

all five occurences of q_k in these three lines should be q_{k-1}

• page 17, line 2

the factorization is of 150, not 3

• page 17, line -10

Proposition 1.10 sould be Proposition 1

• page 19, line 8

Proposition 1.10 sould be Proposition 1.

• pages 23–24, exercise 1.18, part (c)

Change the first sentence of this part to read: "If gcd(a,b) = 1, then the s- and t-sequences from the last occurring 1 on, when viewed in reverse and ignoring the minus signs, are Euclidean algorithm remainder sequences starting from b and a, respectively." The last sentence that begins "Note one small exception ..." can be dropped.

• page 24, exercise 1.26

add to end of sentence: "and of opposite parity."

• page 30, end of exercise 1.37
end of sentence is missing. It should be "for t_n in terms of a modular inverse in the d>1 case."
• page 35, line 1:
change "if there is some constant c" to "if, for sufficiently large N, there is some constant c"
• page 47, line 9-10:
Replace "Exactly half ....2.7)." to

In the case of just two integers a and b, exactly half of the integers
between 0 and the conductor are representable (Exercise 2.7).
• page 47, line 11:
change "pairwise coprime positive integers" to "positive integers with greatest common divisor equal to 1"
• page 56, Proof of Theorem 2.6:
change the definition of Y to {0, a, 2a, 3a, ..., (p-1)a}

following the definition of Y, mod m should be mod p (twice)
• page 59
note in the second line of the first piece of code, PrimeQ is used. The reader needs to be aware that this function is only guaranteed to be accurate for integers below 10^16.
• page 60, line 4
2^{2^{341}-1},\cdots should be 2^{2^{341}-1}-1,\cdots
• page 61, last line of first full paragraph

"section 3.7" should be "Section 3.6"

• page 62, line -8
"number" should be "numbers"
• page 64, exercise 2.43
"M. Cipolla, 1904" should be in boldface
assumption can be weakened to "p does not divide b^2-1".
• page 64, exercise 2.44
in the displayed equation
(\gcd(n-1,p-1)-1) should be \gcd(n-1,p-1)
• page 75, line 1
"perfect number" should be "perfect numbers
• page 80, exercise 3.20:
"Here is an" should be "Here is an outline."
• page 82, Theorem 3.7:
"If m>0 and (a,m)=1" should be "If m>0 and gcd(a,m)=1"
• page 82, 2nd last line of proof of Theorem 3.7

"relatively prime to a" should be "relatively prime to m"

• page 82, Corollary 3.8
the hypothesis should be that s is relatively prime to m.
• page 94, line -8
"Corollary 3.21" should be "Corollary 3.8"
• page 99, line -3:
10^267 should be 10^100 + 267
• page 108, caption for Figure 4.3

The interval should be [10^8 - 5000, 10^8 + 5000]

• page 111, exercise 4.7(b) line 2

"the series in (a) is" should be "the series in (a) as"

• page 117, line -3:
2445 should be 245

• page 118, line 10

"would have have to" should be "would have to"

• page 119, Theorem 4.5
i > 2 should be i >= 2
• page 128, exercise 4.14, lines 1-2,

"Exercise 2.41" should be "Exercise 2.40"

• page 134, line -8
"positive integers $m$ that" should be "positive integers that"
• page 140, exercise 4.43
There is only one prime q such that q, 2q+1, and 4q+1 are all prime (q=3). the problem should read:

Suppose q, 6q+1, and 12q+1 are all prime, and n = (6q+1)(12q+1). Prove that the number of strong liars for n is 18q^2. This means that if we could find arbitrarily large primes q for which 6q+1 and 12q+1 are prime (this is an open question), then the proportion of strong liars can be made arbitrarily close to 1/4 infinitely often..
• page 142, Mystery 1

the Lucas test is in 8.2, not 9.2.
• page 145,

paragraph 2, lines 3–4, "secret message" should be "secret messages"

• page 147, paragraph 2, line 8

"HEADS come up" should be "HEADS comes up"

• page 149, bullet 6

"Section 5.5" should be "Section 5.3"

• page 157 Last text paragraph on page
"last three entries" should be "last two entries"
• page 159, line 5 of Proof of Proposition 5.1

"can never by" should be "can never be"

• page 159 first line of last paragraph

"caclulations" should be "calculations"

• page 161, line 6
"commutaive" should be "commutative"
• page 162, second-last line of the proof, the equality involving eight sigma operations, four on each side of =.
There are two extra sigmas. The third sigma on the left side, and the
parens that it corresponds to () should be deleted.

And the third sigma on the right side, and the parens that it corresponds
to () should be deleted.
• page 163, Condition C5: The upper limit on i should be n-1, not n.
• page 164, two lines after the displayed equation in the middle of the page: i <= n should be i < n.
• page 165, last line before Exercises

"string can be" should be "string to be"

• page 173, Algorithm 5.3
as written, the code wastes time accumulating prod; corrected code can be obtained by clicking here
• page 179, line -3,
"As we saw in the last chapter," should be "As we saw in Chapter 4,"
• page 180, line 14,
"We know from Theorem 4.4" should be "We know from Theorem 4.5"
• page 185, third displayed equation

congruence should be an equality

• page 186, last displayed equation,
equalities should be congruences
• page 187, line 5 under "Proof of Quadratic Recipority"

"then $r_j'$" should be "then $r_j'$ is odd"

• page 187, first line of second paragraph under "Proof of Quadratic Reciprocity"

"where a runs over", the "a" should be italicized.

• page 189, first displayed equation,
subscript n should be r
• page 189, line -8

"chapters" should be "chapter"

• pag 192, 6th displayed equation

122019 should be 12219

• page 198, Exercise 6.24 (e)
question should conclude "when $a$ is odd."
• page 198, Exercise 6.25
s=e should be s >= e
• page 202, line 4
"each a_i is a positive integer" should be "a_0 is a nonnegative integer and each a_i, i>= 1, is a positive integer"
• page 208, end of proof of Theorem 7.4 (a)
Last sentence should read: "But this follows from Propositions 7.2(d) and 7.3(b)."
• page 216, fourth line of text, last item: should be (2 + Sqrt[2])/4, not (2 - Sqrt[2])/4.
• page 227, Exercise 7.29 (e)
r in the first line should have subscript n; in the second line the first q sub n should be (q sub n) + 1
• page 233, line -9,
"the underlined condition" should be "the italicized condition"
• p. 233, Wurm section, line 4 should read:
..where W, X, Y, and Z denote number of ... and w, x, y, z similarly denote the cows.
• page 233, lines -8 & -7,
"where X, Y, Z, and W denote ... and x, y, z, w similarly denote" should be "where W, X, Y, and Z denote ... and w, x, y, z similarly denote"
• page 236, line -2,
"because those dvidsors of are" should be "because those divisors of 2329 are"
• page 237, first display:
the 4729492 in the second denominator should be 4729494
• page 237, lines 15–17:
"ceiling" should be "floor", and in the displayed equation, the ceiling should be replaced by the floor
• page 247, lines 4 and 5 from bottom

definition of discriminant should be the largest square-free integer that divides $d = P^2 - 4Q$ and such that $d$ divided by the discriminant is a perfect square.

• p. 249, Theorem 8.1
change title of theorem to "An Extension of the Classic Fermat's Little Theorem"
• p. 257, Proof of Corollary 8.8
Last sentence should read: If $n = p^t$ and $t > 1$ then Theorem 8.6 states that $\omega(n)$ divides $p^t \pm p^{t-1}$, and $p^t \pm 1$ divides $p^t \pm p^{t-1}$ if and only if $t = 1$.

• p. 259, problem 8.2
in the displayed equation, replace a and b by alpha and overline{alpha}, respectively
• p. 264, line -5 of text
Exer. 1.39 should be 1.38
• page 274, line 1
\alpha^{n-\epsilon(n)}\equiv 2Q
should be \alpha^{n-\epsilon(n)}\equiv Q^{\frac{1-\epsilon(n)}2}
• p. 274, line 8 of text
"..., n+1" should be "..., n-epsilon(n)"
• p.289, seventh bullet

1, 2, 3, ..., 156 should be 1, 2, 3, ... 155
• p. 297, Figure 9.5 caption
change "convergent" to "convergence"
• p. 307, Theorem 9.9, part (a) should read
+- alpha or +- i alpha is a rational prime congruent to 3 (mod 4), or
• p. 315, second sentence of first paragraph of text
change "But D.Gordon and G.Rodemich[GR] found ..." to "But N. Jarvis (see [GR]) found ..."
• p. 322, exercise 9.39
change (Gordon and Rodemich [GR]) to (N. Jarvis; see [GR])
• p. 330 line 2

"[ELs]" should be "[ELS]", remove reference [Mol]

• page 357, S. Wolfram
publication year should be 1999
• page 361, PseudoprimeQ

first reference should be to page 59 instead of page 69

Thanks to Ellen Gethner, Jeff Shallit , Kevin Ford, Gove Effinger, Duncan Buell , Peter Hackman, Jon Mormino, Jeff Nunemacher, Shareef Tayara, Yuri Matijasevic, Raymund Breu, Zhang Zhenxiang, Jacob Bond, Eric Weisser, Beltraminelli Stefano, and Marvin Schaefer for help in finding errors.