ALL 48 CHAPTERS COVERED
SOLUTIONS MANUAL
, Table of Contents
Chapter 1 What is Number Theory? 1
Chapter 2 Pythagorean Triples 5
Chapter 3 Pythagorean Triples and the Unit Circle 11
Chapter 4 Sums of Higher Powers and Fermat’s Last Theorem 16
Chapter 5 Divisibility and the Greatest Common Divisor 19
Chapter 6 Linear Equations and the Greatest Common Divisor 25
Chapter 7 Factorization and the Fundamental Theorem of Arithmetic 30
Chapter 8 Congruences 35
Chapter 9 Congruences, Powers, and Fermat’s Little Theorem 40
Chapter 10 Congruences, Powers, and Euler’s Formula 43
Chapter 11 Euler’s Phi Function and the Chinese Remainder Theorem 46
Chapter 12 Prime Numbers 55
Chapter 13 Counting Primes 60
Chapter 14 Mersenne Primes 65
Chapter 15 Mersenne Primes and Perfect Numbers 68
Chapter 16 Powers Modulo m and Successive Squaring 75
Chapter 17 Computing kth Roots Modulo m 78
Chapter 18 Powers, Roots, and “Unbreakable” Codes 81
Chapter 19 Primality Testing and Carmichael Numbers 84
Chapter 20 Squares Modulo p 88
Chapter 21 Is -1 a Square Modulo p? Is 2? 91
Chapter 22 Quadratic Reciprocity 95
Chapter 23 Which Primes are Sums of Two Squares? 108
Chapter 24 Which Numbers are Sums of Two Squares? 113
Chapter 25 As Easy as One, Two, Three 116
Chapter 26 Euler’s Phi Function and Sums of Divisors 122
Chapter 27 Powers Modulo p and Primitive Roots 126
Chapter 28 Primitive Roots and Indices 135
Chapter 29 The Equation X4 + Y4 = Z4 138
Chapter 30 Square-Triangular Numbers Revisited 143
Chapter 31 Pell’s Equation 147
Chapter 32 Diophantine Approximation 152
Chapter 33 Diophantine Approximation and Pell’s Equation 156
Chapter 34 Number Theory and Imaginary Numbers 159
Chapter 35 The Gaussian Integers and Unique Factorization 163
Chapter 36 Irrational Numbers and Transcendental Numbers 168
Chapter 37 Binomial Coefficients and Pascal’s Triangle 176
Chapter 38 Fibonacci’s Rabbits and Linear Recurrence Sequences 180
Chapter 39 Oh, What a Beautiful Function 190
Chapter 40 Cubic Curves and Elliptic Curves 195
Chapter 41 Elliptic Curves with Few Rational Points 200
Chapter 42 Points on Elliptic Curves Modulo p 205
Chapter 43 Torsion Collections Modulo p and Bad Primes 211
Chapter 44 Defect Bounds and Modularity Patterns 215
© 2013, Pearson Education, Inc.
,Chapter 45 The Topsy-Turvy World of Continued Fractions [online] 219
Chapter 46 Continued Fractions, Square Roots, and Pell’s Equation [online] 227
Chapter 47 Generating Functions [online] 232
Chapter 48 Sums of Powers [online] 240
© 2013, Pearson Education, Inc.
,Chapter 1
What Is Number Theory?
Exercises
1.1. The first two numbers that are both squares and triangles are 1 and 36. Find the
next one and, if possible, the one after that. Can you figure out an efficient way to find
triangular-square numbers? Do you think that there are infinitely many?
Solution to Exercise 1.1.
The first three triangular-square numbers are 36, 1225, and 41616. Triangular-square
numbers are given by pairs (m, n) satisfying m(m +1)/2=n2. The first few pairs are
(8, 6), (49, 35), (288, 204), (1681, 1189), and (9800, 6930). The pattern for generating
these pairs is quite subtle. We will give a complete description of all triangular-square
numbers in Chapter 28, but for now it would be impressive to merely notice empirically
that if (m, n) gives a triangular-square number, then so does (3m +4n +1, 2m +3n +1).
Starting with (1, 1) and applying this rule repeatedly will actually give all triangular-square
numbers.
1.2. Try adding up the first few odd numbers and see if the numbers you get satisfy some
sort of pattern. Once you find the pattern, express it as a formula. Give a geometric
verification that your formula is correct.
Solution to Exercise 1.2.
The sum of the first n odd numbers is always a square. The formula is
1 + 3 + 5 + 7 + •• • + (2n - 1) = n2.
The following pictures illustrate the first few cases, and they make it clear how the general
case works.
7777
555
33 5557
335
13 3357
135
1357
1+3=4 1+3+5=9 1+3+5+7=16
1
© 2013, Pearson Education, Inc.
,[Chap. 1] What Is Number Theory? 2
1.3. The consecutive odd numbers 3, 5, and 7 are all primes. Are there infinitely many
such “prime triplets”? That is, are there infinitely many prime numbers p such that p +2
and p +4are also primes?
Solution to Exercise 1.3.
The only prime triplet is 3, 5, 7. The reason is that for any three odd numbers, at least one
of them must be divisible by 3. So in order for them all to be prime, one of them must
equal 3. It is conjectured that there are infinitely many primes p such that p +2and p +6
are prime, but this has not been proved. Similarly, it is conjectured that there are infinitely
many primes p such that p +4and p +6are prime, but again no one has a proof.
1.4. It is generally believed that infinitely many primes have the form N2 +1, although
no one knows for sure.
(a) Do you think that there are infinitely many primes of the form N2 - 1?
(b) Do you think that there are infinitely many primes of the form N 2 - 2?
(c) How about of the form N2 - 3? How about N2 - 4?
(d) Which values of a do you think give infinitely many primes of the form N 2 - a?
Solution to Exercise 1.4.
First we accumulate some data, which we list in a table. Looking at the table, we see that
N2 - 1 and N2 - 4 are almost never equal to primes, while N2 - 2 and N2 - 3 seem to
be primes reasonably often.
N N2 - 1 N2 - 2 N2 - 3 N2 - 4
2 3 2 1 0
3 8 = 23 7 6= 2•3 5
4 15 = 3 • 5 14 = 2 • 7 13 12 = 22 • 3
5 24 = 23 •3 23 22 = 2 • 11 21 = 3 • 7
6 35 = 5 • 7 34 = 2 • 17 33 = 3 • 11 32 = 25
7 48 = 24 • 3 47 46 = 2 • 23 45 = 32 • 5
8 63 = 32 • 7 62 = 2 • 31 61 60 = 22 • 3 • 5
9 80 = 24 • 5 79 78 = 2 • 3 • 13 77 = 7 • 11
10 99 = 32 • 11 98 = 2 • 72 97 96 = 25 • 3
11 120 = 23 • 3 • 5 119 = 7 • 17 118 = 2 • 59 117 = 32 • 13
12 143 = 11 • 13 142 = 2 • 71 141 = 3 • 47 140 = 22 • 5 • 7
13 168 = 23 • 3 • 7 167 166 = 2 • 83 165 = 3 • 5 • 11
14 195 = 3 • 5 • 13 194 = 2 • 97 193 192 = 26 • 3
15 224 = 25 • 7 223 222 = 2 • 3 • 37 221 = 13 • 17
Looking at the even values of N in the N 2 - 1 column, we might notice that 22 - 1
is a multiple of 3, that 42 - 1 is a multiple of 5, that 62 - 1 is a multiple of 7, and so on.
2
© 2013, Pearson Education, Inc.
,[Chap. 1] What Is Number Theory? 3
Having observed this, we see that the same pattern holds for the odd N’s. Thus 32 - 1 is
a multiple of 4 and 52 - 1 is a multiple of 6 and so on. So we might guess that N 2 - 1
is always a multiple of N +1. This is indeed true, and it can be proved true by the well
known algebraic formula
N2 - 1=(N - 1)(N +1).
So N2 — 1 will never be prime if N > 2.
The N2 - 4 column is similarly explained by the formula
N2—4=(N—2)(N+2).
More generally, if a is a perfect square, say a = b2, then there will not be infinitely many
primes of the form N2 — a, since
N2 —a = N2 —b2 =(N—b)(N+b).
On the other hand, it is believed that there are infinitely many primes of the form
N2 — 2 and infinitely many primes of the form N 2 — 3. Generally, if a is not a perfect
square, it is believed that there are infinitely many primes of the form N 2 — a. But no one
has yet proved any of these conjectures.
1.5. The following two lines indicate another way to derive the formula for the sum of the
first n integers by rearranging the terms in the sum. Fill in the details.
1 + 2 + 3 + ••• + n = (1 + n) + (2 + (n — 1)) + (3 + (n — 2)) + • • •
= (1 + n) + (1 + n) + (1 + n) +------- .
How many copies of n +1 are in there in the second line? You may need to consider the
cases of odd n and even n separately. If that’s not clear, first try writing it out explicitly for
n =6and n =7.
Solution to Exercise 1.5.
Suppose first that n is even. Then we get n/2 copies of 1+n, so the total is
n n2 + n
2 (1 + n) = 2
Next suppose that n is odd. Then we get n-1 copies of 1 + n and also the middle
term n+1 which hasn’t yet been counted. To illustrate with n = 9, we group the terms as
1 + 2 + ••• + 9 = (1 + 9) + (2 + 8) + (3 + 7) + (4 + 6) + 5,
so there are 4 copies of 10, plus the extra 5 that’s left over. For general n, we get
n— 1 n +1 n2 — 1 n +1 n2 + n
—(1 + n) + —= -^ + —= -^
3
© 2013, Pearson Education, Inc.
,[Chap. 1] What Is Number Theory? 4
Another similar way to do this problem that doesn’t involve splitting into cases is to
simply take two copies of each term. Thus
2(1 + 2 + • •• + n) = (1 + 2 + •• • + n) + (1 + 2 + • •• + n)
= (1 + 2 + •• • + n) + (n + •• • + 2 + 1)
=(1+n)+(2+n- 1) + (3+n- 2) + •••+(n+1)
= (1 + n) + (1 + n) +------- + (1 + n)
n copies of n +1
= n(1 + n) = n2 + n
Thus the twice the sum 1 + 2 + • • • + n equal n2 + n, and now divide by 2 to get the answer.
1.6. For each of the following statements, fill in the blank with an easy-to-check crite
rion:
(a) M is a triangular number if and only if is an odd square.
(b) N is an odd square if and only if is a triangular number.
(c) Prove that your criteria in (a) and (b) are correct.
Solution to Exercise 1.6.
(a) M is a triangular number if and only if 1+8M is an odd square.
(b) N is an odd square if and only if (N - 1)/8 is a triangular number. (Note that if N is
an odd square, then N2 - 1 is divisible by 8, since (2k +1)2 = 4k(k+1)+1, and 4k(k +1)
is a multiple of 8.)
(c) If M is triangular, then M = m(m+1)/2, so 1+8M = 1+4m+4m2 = (1+2m)2.
Conversely, if 1+8M is an odd square, say 1+8M =(1+2k)2, then solving for M
gives M =(k + k2)/2, so M is triangular.
Next suppose N is an odd square, say N =(2k +1)2 . Then as noted above, (N -
1)/8 = k(k+1)/2, so (N - 1)/8 is triangular. Conversely, if (N - 1)/8 is trianglular, then
(N- 1)/8 = (m2 +m)/2 for some m, so solving for N we find that N = 1+4m+4m2 =
(1 + 2m)2 ,soN is a square.
4
© 2013, Pearson Education, Inc.
,Chapter 2
Pythagorean Triples
Exercises
2.1. (a) We showed that in any primitive Pythagorean triple (a, b, c), either a or b is even.
Use the same sort of argument to show that either a or b must be a multiple of 3.
(b) By examining the above list of primitive Pythagorean triples, make a guess about
when a, b,orc is a multiple of 5. Try to show that your guess is correct.
Solution to Exercise 2.1.
(a) If a is not a multiple of 3, it must equal either 3x +1 or 3x +2. Similarly, if b is not
a multiple of 3, it must equal 3y +1or 3y +2. There are four possibilities for a2 + b2,
namely
a2+b2 =(3x+1)2+(3y+1)2 =9x2 +6x+1+9y2 +6y+1
=3(3x2+2x+3y2+2y)+2,
a2+b2 =(3x+1)2+(3y+2)2 =9x2 +6x+1+9y2 +12y+4
=3(3x2+2x+3y2+4y+1)+2,
a2+b2 =(3x+2)2+(3y+1)2 =9x2 +12x+4+9y2 +6y+1
=3(3x2+4x+3y2+2y+1)+2,
a2+b2 =(3x+2)2+(3y+2)2 =9x2 +12x+4+9y2 +12y+4
= 3(3x2 +4x+3y2+4y+2)+2.
So if a and b are not multiples of 3, then c2 = a2 + b2 looks like 2 more than a multiple
of 3. But regardless of whether c is 3z or 3z+1or 3z+2, the numbers c2 cannot be 2 more
than a multiple of 3. This is true because
(32)2 =3 • 3z,
(3z +1)2 = 3(3z2 +2z)+1,
(3z + 2)2 = 3(3z2 +4z+1)+1.
5
© 2013, Pearson Education, Inc.
,[Chap. 2] Pythagorean Triples 6
(b) The table suggests that in every primitive Pythagorean triple, exactly one of a, b,orc
is a multiple of 5. To verify this, we use the Pythagorean Triples Theorem to write a and b
as a = st and b = 1 (s2 — 12). If either s or t is a multiple of 5, then a is a multiple of 5
and we’re done. Otherwise s looks like s =5S + i and t looks like 5T + j with i and j
being integers in the set {1, 2, 3, 4}. Next we observe that
2b=s2 —t2 =(5S+i)2 — (5T +j)2 = 25(S2 —T2)+10(Si—Tj)+i2 —j2.
If i2 — j2 is a multiple of 5, then b is a multiple of 5, and again we’re done. Looking at
the 16 possibilities for the pair (i, j), we see that this accounts for 8 of them, leaving the
possibilities
(i,j) = (1,2), (1, 3), (2, 1), (2, 4), (3, 1), (3, 4), (4, 2), or (4, 3).
Now for each of these remaining possibilities, we need to check that
2c=s2 +t2 =(5S+i)2 +(5T+j)2 =25(S2+T2)+10(Si+Tj)+i2 +j2
is a multiple of 5, which means checking that i2 + j 2 is a multiple of 5. This is easily
accomplished:
12 +22 =5 12 +32 = 1021 + 12 =5 22 +42 =20 (2.1)
31 +12 = 1032 +42 = 2542 +22 = 2042 +32 =25. (2.2)
2.2. A nonzero integer d is said to divide an integer m if m = dk for some number k.
Show that if d divides both m and n, then d also divides m — n and m + n.
Solution to Exercise 2.2.
Both m and n are divisible by d, so m = dk and n = dk'. Thus m ± n = dk ± dk' =
d(k ± k'), so m + n and m — n are divisible by d.
2.3. For each of the following questions, begin by compiling some data; next examine the
data and formulate a conjecture; and finally try to prove that your conjecture is correct. (But
don’t worry if you can’t solve every part of this problem; some parts are quite difficult.)
(a) Which odd numbers a can appear in a primitive Pythagorean triple (a, b, c)?
(b) Which even numbers b can appear in a primitive Pythagorean triple (a, b, c)?
(c) Which numbers c can appear in a primitive Pythagorean triple (a, b, c)?
Solution to Exercise 2.3.
(a) Any odd number can appear as the a in a primitive Pythagorean triple. To find such a
triple, we can just take t = a and s =1in the Pythagorean Triples Theorem. This gives
the primitive Pythagorean triple (a, (a2 — 1)/2, (a2 + 1)/2).
(b) Looking at the table, it seems first that b must be a multiple of 4, and second that
every multiple of 4 seems to be possible. We know that b looks like b =(s2 — t2)/2 with
6
© 2013, Pearson Education, Inc.
, [Chap. 2] Pythagorean Triples 7
s and t odd. This means we can write s =2m +1and t =2n +1. Multiplying things out
gives
(
b = (2m +1) - 2n +1) = 2m2 + 2m - 2n2 - 2n
= 2m(m +1)- 2n(n +1).
Can you see that m(m +1)and n(n + 1) must both be even, regardless of the value of m
and n?Sob must be divisible by 4.
On the other hand, if b is divisible by 4, then we can write it as b =2r B for some
odd number B and some r > 2. Then we can try to find values of s and t such that
(s2 - t2 )/2=b. We factor this as
(s-t)(s+t)=2b = 2r+1B.
Now both s - t and s + t must be even (since s and t are odd), so we might try
s - t =2r and s + t =2B.
Solving for s and t gives s = 2r-1 + B and t = -2r-1 + B. Notice that s and t are odd,
since B is odd and r > 2. Then
a=st=B2 - 22r-2,
s2 - t2
b =--------- = 2r B,
2 ,
c = 32+12 = B 2 + 22 r-2
2
This gives a primitive Pythagorean triple with the right value of b provided that B > 2r-1.
On the other hand, if B < 2r-1, then we can just take a = 22r-2 - B2 instead.
(c) This part is quite difficult to prove, and it’s not even that easy to make the correct
conjecture. It turns out that an odd number c appears as the hypotenuse of a primitive
Pythagorean triple if and only if every prime dividing c leaves a remainder of 1 when
divided by 4. Thus c appears if it is divisible by the primes 5, 13, 17, 29, 37,..., but it
does not appear if it is divisible by any of the primes 3, 7, 11, 19, 23,..... We will prove
this in Chapter 25. Note that it is not enough that c itself leave a remainder of 1 when
divided by 4. For example, neither 9 nor 21 can appear as the hypotenuse of a primitive
Pythagorean triple.
2.4. In our list of examples are the two primitive Pythagorean triples
332 +562 =652 and 162 +632 = 652.
Find at least one more example of two primitive Pythagorean triples with the same value
of c. Can you find three primitive Pythagorean triples with the same c? Can you find more
than three?
7
© 2013, Pearson Education, Inc.
SOLUTIONS MANUAL
, Table of Contents
Chapter 1 What is Number Theory? 1
Chapter 2 Pythagorean Triples 5
Chapter 3 Pythagorean Triples and the Unit Circle 11
Chapter 4 Sums of Higher Powers and Fermat’s Last Theorem 16
Chapter 5 Divisibility and the Greatest Common Divisor 19
Chapter 6 Linear Equations and the Greatest Common Divisor 25
Chapter 7 Factorization and the Fundamental Theorem of Arithmetic 30
Chapter 8 Congruences 35
Chapter 9 Congruences, Powers, and Fermat’s Little Theorem 40
Chapter 10 Congruences, Powers, and Euler’s Formula 43
Chapter 11 Euler’s Phi Function and the Chinese Remainder Theorem 46
Chapter 12 Prime Numbers 55
Chapter 13 Counting Primes 60
Chapter 14 Mersenne Primes 65
Chapter 15 Mersenne Primes and Perfect Numbers 68
Chapter 16 Powers Modulo m and Successive Squaring 75
Chapter 17 Computing kth Roots Modulo m 78
Chapter 18 Powers, Roots, and “Unbreakable” Codes 81
Chapter 19 Primality Testing and Carmichael Numbers 84
Chapter 20 Squares Modulo p 88
Chapter 21 Is -1 a Square Modulo p? Is 2? 91
Chapter 22 Quadratic Reciprocity 95
Chapter 23 Which Primes are Sums of Two Squares? 108
Chapter 24 Which Numbers are Sums of Two Squares? 113
Chapter 25 As Easy as One, Two, Three 116
Chapter 26 Euler’s Phi Function and Sums of Divisors 122
Chapter 27 Powers Modulo p and Primitive Roots 126
Chapter 28 Primitive Roots and Indices 135
Chapter 29 The Equation X4 + Y4 = Z4 138
Chapter 30 Square-Triangular Numbers Revisited 143
Chapter 31 Pell’s Equation 147
Chapter 32 Diophantine Approximation 152
Chapter 33 Diophantine Approximation and Pell’s Equation 156
Chapter 34 Number Theory and Imaginary Numbers 159
Chapter 35 The Gaussian Integers and Unique Factorization 163
Chapter 36 Irrational Numbers and Transcendental Numbers 168
Chapter 37 Binomial Coefficients and Pascal’s Triangle 176
Chapter 38 Fibonacci’s Rabbits and Linear Recurrence Sequences 180
Chapter 39 Oh, What a Beautiful Function 190
Chapter 40 Cubic Curves and Elliptic Curves 195
Chapter 41 Elliptic Curves with Few Rational Points 200
Chapter 42 Points on Elliptic Curves Modulo p 205
Chapter 43 Torsion Collections Modulo p and Bad Primes 211
Chapter 44 Defect Bounds and Modularity Patterns 215
© 2013, Pearson Education, Inc.
,Chapter 45 The Topsy-Turvy World of Continued Fractions [online] 219
Chapter 46 Continued Fractions, Square Roots, and Pell’s Equation [online] 227
Chapter 47 Generating Functions [online] 232
Chapter 48 Sums of Powers [online] 240
© 2013, Pearson Education, Inc.
,Chapter 1
What Is Number Theory?
Exercises
1.1. The first two numbers that are both squares and triangles are 1 and 36. Find the
next one and, if possible, the one after that. Can you figure out an efficient way to find
triangular-square numbers? Do you think that there are infinitely many?
Solution to Exercise 1.1.
The first three triangular-square numbers are 36, 1225, and 41616. Triangular-square
numbers are given by pairs (m, n) satisfying m(m +1)/2=n2. The first few pairs are
(8, 6), (49, 35), (288, 204), (1681, 1189), and (9800, 6930). The pattern for generating
these pairs is quite subtle. We will give a complete description of all triangular-square
numbers in Chapter 28, but for now it would be impressive to merely notice empirically
that if (m, n) gives a triangular-square number, then so does (3m +4n +1, 2m +3n +1).
Starting with (1, 1) and applying this rule repeatedly will actually give all triangular-square
numbers.
1.2. Try adding up the first few odd numbers and see if the numbers you get satisfy some
sort of pattern. Once you find the pattern, express it as a formula. Give a geometric
verification that your formula is correct.
Solution to Exercise 1.2.
The sum of the first n odd numbers is always a square. The formula is
1 + 3 + 5 + 7 + •• • + (2n - 1) = n2.
The following pictures illustrate the first few cases, and they make it clear how the general
case works.
7777
555
33 5557
335
13 3357
135
1357
1+3=4 1+3+5=9 1+3+5+7=16
1
© 2013, Pearson Education, Inc.
,[Chap. 1] What Is Number Theory? 2
1.3. The consecutive odd numbers 3, 5, and 7 are all primes. Are there infinitely many
such “prime triplets”? That is, are there infinitely many prime numbers p such that p +2
and p +4are also primes?
Solution to Exercise 1.3.
The only prime triplet is 3, 5, 7. The reason is that for any three odd numbers, at least one
of them must be divisible by 3. So in order for them all to be prime, one of them must
equal 3. It is conjectured that there are infinitely many primes p such that p +2and p +6
are prime, but this has not been proved. Similarly, it is conjectured that there are infinitely
many primes p such that p +4and p +6are prime, but again no one has a proof.
1.4. It is generally believed that infinitely many primes have the form N2 +1, although
no one knows for sure.
(a) Do you think that there are infinitely many primes of the form N2 - 1?
(b) Do you think that there are infinitely many primes of the form N 2 - 2?
(c) How about of the form N2 - 3? How about N2 - 4?
(d) Which values of a do you think give infinitely many primes of the form N 2 - a?
Solution to Exercise 1.4.
First we accumulate some data, which we list in a table. Looking at the table, we see that
N2 - 1 and N2 - 4 are almost never equal to primes, while N2 - 2 and N2 - 3 seem to
be primes reasonably often.
N N2 - 1 N2 - 2 N2 - 3 N2 - 4
2 3 2 1 0
3 8 = 23 7 6= 2•3 5
4 15 = 3 • 5 14 = 2 • 7 13 12 = 22 • 3
5 24 = 23 •3 23 22 = 2 • 11 21 = 3 • 7
6 35 = 5 • 7 34 = 2 • 17 33 = 3 • 11 32 = 25
7 48 = 24 • 3 47 46 = 2 • 23 45 = 32 • 5
8 63 = 32 • 7 62 = 2 • 31 61 60 = 22 • 3 • 5
9 80 = 24 • 5 79 78 = 2 • 3 • 13 77 = 7 • 11
10 99 = 32 • 11 98 = 2 • 72 97 96 = 25 • 3
11 120 = 23 • 3 • 5 119 = 7 • 17 118 = 2 • 59 117 = 32 • 13
12 143 = 11 • 13 142 = 2 • 71 141 = 3 • 47 140 = 22 • 5 • 7
13 168 = 23 • 3 • 7 167 166 = 2 • 83 165 = 3 • 5 • 11
14 195 = 3 • 5 • 13 194 = 2 • 97 193 192 = 26 • 3
15 224 = 25 • 7 223 222 = 2 • 3 • 37 221 = 13 • 17
Looking at the even values of N in the N 2 - 1 column, we might notice that 22 - 1
is a multiple of 3, that 42 - 1 is a multiple of 5, that 62 - 1 is a multiple of 7, and so on.
2
© 2013, Pearson Education, Inc.
,[Chap. 1] What Is Number Theory? 3
Having observed this, we see that the same pattern holds for the odd N’s. Thus 32 - 1 is
a multiple of 4 and 52 - 1 is a multiple of 6 and so on. So we might guess that N 2 - 1
is always a multiple of N +1. This is indeed true, and it can be proved true by the well
known algebraic formula
N2 - 1=(N - 1)(N +1).
So N2 — 1 will never be prime if N > 2.
The N2 - 4 column is similarly explained by the formula
N2—4=(N—2)(N+2).
More generally, if a is a perfect square, say a = b2, then there will not be infinitely many
primes of the form N2 — a, since
N2 —a = N2 —b2 =(N—b)(N+b).
On the other hand, it is believed that there are infinitely many primes of the form
N2 — 2 and infinitely many primes of the form N 2 — 3. Generally, if a is not a perfect
square, it is believed that there are infinitely many primes of the form N 2 — a. But no one
has yet proved any of these conjectures.
1.5. The following two lines indicate another way to derive the formula for the sum of the
first n integers by rearranging the terms in the sum. Fill in the details.
1 + 2 + 3 + ••• + n = (1 + n) + (2 + (n — 1)) + (3 + (n — 2)) + • • •
= (1 + n) + (1 + n) + (1 + n) +------- .
How many copies of n +1 are in there in the second line? You may need to consider the
cases of odd n and even n separately. If that’s not clear, first try writing it out explicitly for
n =6and n =7.
Solution to Exercise 1.5.
Suppose first that n is even. Then we get n/2 copies of 1+n, so the total is
n n2 + n
2 (1 + n) = 2
Next suppose that n is odd. Then we get n-1 copies of 1 + n and also the middle
term n+1 which hasn’t yet been counted. To illustrate with n = 9, we group the terms as
1 + 2 + ••• + 9 = (1 + 9) + (2 + 8) + (3 + 7) + (4 + 6) + 5,
so there are 4 copies of 10, plus the extra 5 that’s left over. For general n, we get
n— 1 n +1 n2 — 1 n +1 n2 + n
—(1 + n) + —= -^ + —= -^
3
© 2013, Pearson Education, Inc.
,[Chap. 1] What Is Number Theory? 4
Another similar way to do this problem that doesn’t involve splitting into cases is to
simply take two copies of each term. Thus
2(1 + 2 + • •• + n) = (1 + 2 + •• • + n) + (1 + 2 + • •• + n)
= (1 + 2 + •• • + n) + (n + •• • + 2 + 1)
=(1+n)+(2+n- 1) + (3+n- 2) + •••+(n+1)
= (1 + n) + (1 + n) +------- + (1 + n)
n copies of n +1
= n(1 + n) = n2 + n
Thus the twice the sum 1 + 2 + • • • + n equal n2 + n, and now divide by 2 to get the answer.
1.6. For each of the following statements, fill in the blank with an easy-to-check crite
rion:
(a) M is a triangular number if and only if is an odd square.
(b) N is an odd square if and only if is a triangular number.
(c) Prove that your criteria in (a) and (b) are correct.
Solution to Exercise 1.6.
(a) M is a triangular number if and only if 1+8M is an odd square.
(b) N is an odd square if and only if (N - 1)/8 is a triangular number. (Note that if N is
an odd square, then N2 - 1 is divisible by 8, since (2k +1)2 = 4k(k+1)+1, and 4k(k +1)
is a multiple of 8.)
(c) If M is triangular, then M = m(m+1)/2, so 1+8M = 1+4m+4m2 = (1+2m)2.
Conversely, if 1+8M is an odd square, say 1+8M =(1+2k)2, then solving for M
gives M =(k + k2)/2, so M is triangular.
Next suppose N is an odd square, say N =(2k +1)2 . Then as noted above, (N -
1)/8 = k(k+1)/2, so (N - 1)/8 is triangular. Conversely, if (N - 1)/8 is trianglular, then
(N- 1)/8 = (m2 +m)/2 for some m, so solving for N we find that N = 1+4m+4m2 =
(1 + 2m)2 ,soN is a square.
4
© 2013, Pearson Education, Inc.
,Chapter 2
Pythagorean Triples
Exercises
2.1. (a) We showed that in any primitive Pythagorean triple (a, b, c), either a or b is even.
Use the same sort of argument to show that either a or b must be a multiple of 3.
(b) By examining the above list of primitive Pythagorean triples, make a guess about
when a, b,orc is a multiple of 5. Try to show that your guess is correct.
Solution to Exercise 2.1.
(a) If a is not a multiple of 3, it must equal either 3x +1 or 3x +2. Similarly, if b is not
a multiple of 3, it must equal 3y +1or 3y +2. There are four possibilities for a2 + b2,
namely
a2+b2 =(3x+1)2+(3y+1)2 =9x2 +6x+1+9y2 +6y+1
=3(3x2+2x+3y2+2y)+2,
a2+b2 =(3x+1)2+(3y+2)2 =9x2 +6x+1+9y2 +12y+4
=3(3x2+2x+3y2+4y+1)+2,
a2+b2 =(3x+2)2+(3y+1)2 =9x2 +12x+4+9y2 +6y+1
=3(3x2+4x+3y2+2y+1)+2,
a2+b2 =(3x+2)2+(3y+2)2 =9x2 +12x+4+9y2 +12y+4
= 3(3x2 +4x+3y2+4y+2)+2.
So if a and b are not multiples of 3, then c2 = a2 + b2 looks like 2 more than a multiple
of 3. But regardless of whether c is 3z or 3z+1or 3z+2, the numbers c2 cannot be 2 more
than a multiple of 3. This is true because
(32)2 =3 • 3z,
(3z +1)2 = 3(3z2 +2z)+1,
(3z + 2)2 = 3(3z2 +4z+1)+1.
5
© 2013, Pearson Education, Inc.
,[Chap. 2] Pythagorean Triples 6
(b) The table suggests that in every primitive Pythagorean triple, exactly one of a, b,orc
is a multiple of 5. To verify this, we use the Pythagorean Triples Theorem to write a and b
as a = st and b = 1 (s2 — 12). If either s or t is a multiple of 5, then a is a multiple of 5
and we’re done. Otherwise s looks like s =5S + i and t looks like 5T + j with i and j
being integers in the set {1, 2, 3, 4}. Next we observe that
2b=s2 —t2 =(5S+i)2 — (5T +j)2 = 25(S2 —T2)+10(Si—Tj)+i2 —j2.
If i2 — j2 is a multiple of 5, then b is a multiple of 5, and again we’re done. Looking at
the 16 possibilities for the pair (i, j), we see that this accounts for 8 of them, leaving the
possibilities
(i,j) = (1,2), (1, 3), (2, 1), (2, 4), (3, 1), (3, 4), (4, 2), or (4, 3).
Now for each of these remaining possibilities, we need to check that
2c=s2 +t2 =(5S+i)2 +(5T+j)2 =25(S2+T2)+10(Si+Tj)+i2 +j2
is a multiple of 5, which means checking that i2 + j 2 is a multiple of 5. This is easily
accomplished:
12 +22 =5 12 +32 = 1021 + 12 =5 22 +42 =20 (2.1)
31 +12 = 1032 +42 = 2542 +22 = 2042 +32 =25. (2.2)
2.2. A nonzero integer d is said to divide an integer m if m = dk for some number k.
Show that if d divides both m and n, then d also divides m — n and m + n.
Solution to Exercise 2.2.
Both m and n are divisible by d, so m = dk and n = dk'. Thus m ± n = dk ± dk' =
d(k ± k'), so m + n and m — n are divisible by d.
2.3. For each of the following questions, begin by compiling some data; next examine the
data and formulate a conjecture; and finally try to prove that your conjecture is correct. (But
don’t worry if you can’t solve every part of this problem; some parts are quite difficult.)
(a) Which odd numbers a can appear in a primitive Pythagorean triple (a, b, c)?
(b) Which even numbers b can appear in a primitive Pythagorean triple (a, b, c)?
(c) Which numbers c can appear in a primitive Pythagorean triple (a, b, c)?
Solution to Exercise 2.3.
(a) Any odd number can appear as the a in a primitive Pythagorean triple. To find such a
triple, we can just take t = a and s =1in the Pythagorean Triples Theorem. This gives
the primitive Pythagorean triple (a, (a2 — 1)/2, (a2 + 1)/2).
(b) Looking at the table, it seems first that b must be a multiple of 4, and second that
every multiple of 4 seems to be possible. We know that b looks like b =(s2 — t2)/2 with
6
© 2013, Pearson Education, Inc.
, [Chap. 2] Pythagorean Triples 7
s and t odd. This means we can write s =2m +1and t =2n +1. Multiplying things out
gives
(
b = (2m +1) - 2n +1) = 2m2 + 2m - 2n2 - 2n
= 2m(m +1)- 2n(n +1).
Can you see that m(m +1)and n(n + 1) must both be even, regardless of the value of m
and n?Sob must be divisible by 4.
On the other hand, if b is divisible by 4, then we can write it as b =2r B for some
odd number B and some r > 2. Then we can try to find values of s and t such that
(s2 - t2 )/2=b. We factor this as
(s-t)(s+t)=2b = 2r+1B.
Now both s - t and s + t must be even (since s and t are odd), so we might try
s - t =2r and s + t =2B.
Solving for s and t gives s = 2r-1 + B and t = -2r-1 + B. Notice that s and t are odd,
since B is odd and r > 2. Then
a=st=B2 - 22r-2,
s2 - t2
b =--------- = 2r B,
2 ,
c = 32+12 = B 2 + 22 r-2
2
This gives a primitive Pythagorean triple with the right value of b provided that B > 2r-1.
On the other hand, if B < 2r-1, then we can just take a = 22r-2 - B2 instead.
(c) This part is quite difficult to prove, and it’s not even that easy to make the correct
conjecture. It turns out that an odd number c appears as the hypotenuse of a primitive
Pythagorean triple if and only if every prime dividing c leaves a remainder of 1 when
divided by 4. Thus c appears if it is divisible by the primes 5, 13, 17, 29, 37,..., but it
does not appear if it is divisible by any of the primes 3, 7, 11, 19, 23,..... We will prove
this in Chapter 25. Note that it is not enough that c itself leave a remainder of 1 when
divided by 4. For example, neither 9 nor 21 can appear as the hypotenuse of a primitive
Pythagorean triple.
2.4. In our list of examples are the two primitive Pythagorean triples
332 +562 =652 and 162 +632 = 652.
Find at least one more example of two primitive Pythagorean triples with the same value
of c. Can you find three primitive Pythagorean triples with the same c? Can you find more
than three?
7
© 2013, Pearson Education, Inc.
