David Burton Elementary Number Theory Solutions Chapter 2 Divisibility Theory In The Integers
Page 19 Problem 1 Answer
Here, we have to prove that if a and b are integers, with b > 0 then there exist unique integers q and r satisfying a = qb + r, where 2b ≤ r < 3b
Proof : By division algorithm, ∃ unique q′ and r′, such that a = q′b + r′,0 ≤ r′ < b
∴ a = q′b + r′ + 2b − 2b = (q′−2)b + r′+2b. Let q = q′− 2,r = r′ + 2b,
Therefore r and q are unique.
Since, 0 ≤ r′ < b, then 2b ≤ r′ + 2b < b + 2b ⟹ 2b ≤ r < 3b
Thus, we have proved that if a and b are integers, with b > 0,then there exist unique integers q and r satisfying a = qb + r, where 2b ≤ r < 3b
Page 19 Problem 2 Answer
Here, we have to show that any integer of the form 6k + 5 is also of the form 3j + 2,but not conversely
Proof : If a = 6k + 5 = 3⋅2k + 3 + 2 = 3(2k+1)+ 2 = 3j+ 2 where j = 2k + 1. To disprove that any integer of the form 3j + 2 is also of the form 6k + 5.Take 3j + 2 where j is even, i.e j = 2r ⇒ 3(2r) + 2 = 6r + 2,but r and 2 are unique, so 3j + 2 ≠ 6k + 5
Thus, we proved that any integer of the form 6k + 5 is also of the form 3j + 2, but not conversely
Page 19 Problem 3 Answer
Here, we have to use the Division Algorithm to establish, the square of any integer is either of the form 3k or 3k + 1
Proof : By division algorithm ∃a and q such that a = 3q,a = 3q + 1 or a = 3q + 2
If a = 3q: ∴ a2 = 9q2 = 3(3q2) = 3k where k = 3q2
If a = 3q + 1: ∴ a2 = 9q2 + 6q + 1 = 3(3q2+2q) + 1 = 3k + 1 where k = 3q2 + 2q
If a = 3q + 2: ∴ a2 = 9q2 + 12q + 4 = 9q2 + 12q + 3 + 1 = 3(3q2+4q+1) + 1 = 3k+1 where k = 3q2 + 4q + 1
Thus, we use the Division Algorithm to establish, the square of any integer is either of the form 3k or 3k+1
Here, we have to use the Division Algorithm to establish, the cube of any integer has one of the forms: 9k, 9k+1 or 9k+8
Proof : By division algorithm ∃a and q such that a = 3q+r,r = 0,1,2
If \(a=3 q: (3 q)^3=27 q^3=9\left(3 q^3\right)=9 k \text { where } k=3 q^3\)
If \(a = 3 q+1: (3 q+1)^3=\left(\begin{array}{l}
3 \\
0
\end{array}\right)(3 q)^3+\left(\begin{array}{l}
3 \\
1
\end{array}\right)(3 q)^2+\left(\begin{array}{l}
3 \\
2
\end{array}\right) 3 q+\left(\begin{array}{l}
3 \\
3
\end{array}\right)\)
=\(27 q^3+27 q^2+9 q+1\)
=\(9\left(3 q^3+\right.\left.3 q^2+q\right)+1\)
=\(9 k+1 \text { where } k=3 q^3+3 q^2+q\)
If a = \(3 q+2: (3 q+2)^3=\left(\begin{array}{l}
3 \\
0
\end{array}\right)(3 q)^3+\left(\begin{array}{c}
3 \\
1
\end{array}\right)(3 q)^2 \cdot 2+\left(\begin{array}{l}
3 \\
2
\end{array}\right) 3 q \cdot 2^2+\left(\begin{array}{c}
3 \\
3
\end{array}\right) \cdot 2^3\)
=\(27 q^3+54 q^2+36 q+8\)
= \(9\left(3 q^3+3 q^2+4 q\right)+8=9 k+8 \text { where } k=3 q^3+3 q^2+4 q\)
Thus, we used the Division Algorithm to establish, the cube of any integer has one of the forms : 9k, 9k+1 or 9k+8
Here, we have to use the Division Algorithm to establish the fourth power of any integer is either of the form : 5k, 5k+1
Proof : By division algorithm, ∃a and q such that a = 5q + r,0 ≤ r < 5.Consider n4 = (5q+r)4,from binomial expansion, each term is a factor of 5 except last term.
\((5 q+r)^4=\left(\begin{array}{c}4 \\
0
\end{array}\right)(5 q)^4+\left(\begin{array}{c}
4 \\
1
\end{array}\right)(5 q)^3 r+\left(\begin{array}{c}
4 \\
2
\end{array}\right)(5 q)^2 r^2+\left(\begin{array}{c}
4 \\
1
\end{array}\right)(5 q) r^3+r^4\)
⇒ \((5 q+r)^4=5\left[\left(\begin{array}{c}
4 \\
0
\end{array}\right) 5^3 q^4+\left(\begin{array}{c}
4 \\
1
\end{array}\right) 5^2 q^3 r+\left(\begin{array}{c}
4 \\
2
\end{array}\right) 5 q^2 r^2+\left(\begin{array}{c}
4 \\
1
\end{array}\right) q r^3\right]+r^4\)
⇒ \((5 q+r)^4=5 k+r^4 \text { where } k=\left(\begin{array}{c}
4 \\
0
\end{array}\right) 5^3 q^4+\left(\begin{array}{c}
4 \\
1
\end{array}\right) 5^2 q^3 r+\left(\begin{array}{c}
4 \\
2
\end{array}\right) 5 q^2 r^2+\left(\begin{array}{c}
4 \\
1
\end{array}\right) q r^3\)
If r = 0 then r4 = 0, and n4 = 5k as all other terms have 5 as a factor
If r = 1 then r4 = 1,then clearly n4 = 5k + 1
If r = 2 then r4 = 16 = 15 + 1 = 3⋅5 + 1, so n4 = 5k + 1
If r = 3 then r4 = 81 = 80 + 1 = 5⋅16 + 1, so n4 = 5k + 1
If r = 4 then r4 = 256 = 255 + 1 = 5⋅51 + 1, so n4 = 5k + 1
Thus, we use the Division Algorithm to establish the fourth power of any integer is either of the form 5k or 5k+1
Page 19 Problem 4 Answer
Here, we have to prove that 3a2 − 1 is never a perfect square
Proof :
Suppose 3a2 − 1 = n2, some n by Ex3(a),
3a2 − 1 = 3k + 1 or 3a{2} − 1 = 3k
∴ 3(a2−k) = 2 or 3(a2−k) = 1,
but each are impossible, since by division algorithm, 2 = 3⋅0 + 2 and 1 = 3⋅0 + 1
Thus, we proved that 3a2 − 1 is never a perfect square.
Page 19 Problem 5 Answer
Here, we have to prove that n(n+1)(2n+1)/6 is an integer.
Proof: By division algorithm, ∃n and k such that n = 6k + r, 0 ≤ r < 6. Let A = \(\frac{n(n+1)(2 n+1)}{6}\)
If r = 0 then, A = k(6k+1)(12k+1) is an integer
If r = 1 then
A = \(\frac{(6 k+1)(6 k+2)(12 k+3)}{6}\)
A = \(\frac{(6 k+1) 2(3 k+1) 3(4 k+1)}{6}\)
= (6k+1)(3k+1)(4k+1) is an integer
If r = 2 then
A = \(\frac{(6 k+2)(6 k+3)(12 k+5)}{6}\)
A = \(\frac{2(3 k+1) 3(2 k+1) (12 k+5)}{6}\)
= (6k+1)(3k+1)(4k+1) is an integer
If r = 3 then,
A = \(\frac{(6 k+3)(6 k+4)(12 k+7)}{6}\)
A = \(\frac{3(2 k+1) 2(3 k+1) (12 k+7)}{6}\)
= (2k+1)(3k+2)(12k+7) is an integer
If r = 4 then
A = \(\frac{(6 k+4)(6 k+5)(12 k+9)}{6}\)
A = \(\frac{2(3 k+2) (6 k+5) 3(4 k+3)}{6}\)
= (3k+2)(6k+5)(4k+3) is an integer
If r = 5 then,
A = \(\frac{(6 k+5)(6 k+6)(12 k+11)}{6}\)
A = \(\frac{(6 k+5) 6( k+1) (12 k+11)}{6}\)
= (6k+1)(3k+1)(4k+1) is an integer
Thus for n ≥ 1, \(\frac{n(n+1)(2 n+1)}{6}\) is an integer.
Thus, we prove that for n ≥ 1 n(n+1)(2n+1)/6 is an integer
Page 19 Problem 6 Answer
Here, we have to show that the cube of any integer is of the form 7k or 7k ± 1
Proof : By division algorithm, ∃n and q such that n = 7q + r,0 ≤ r < 7.Consider n3 = (7q+r)3,from binomial expansion, each term is a factor of 7 except last term,
(7q+r)3 = \(\left(\begin{array}{l}
3 \\
0
\end{array}\right)(7 q)^3+\left(\begin{array}{l}
3 \\
1
\end{array}\right)(7 q)^2 r+\left(\begin{array}{l}
3 \\
2
\end{array}\right)(7 q)^2 r^2+r^3\)
If r = 0 then, r3 = 0and n3 = 7k as all other terms have 7 as a factor.
If r = 1then, r3 = 1,then clearly n3 = 7k + 1
If r = 2then,
r3 = 8 = 7 + 1, so n3 = 7k + 1
If r = 3then,
r3 = 27 = 28 − 1 = 4⋅7 − 1, sо n3 = 7k − 1
If r = 4then,
r3 = 64 = 63 + 1 = 9⋅7 + 1, and n3 = 7k + 1
If r = 5then,
r3 = 125 = 126−1 = 18⋅7 − 1, so n3 = 7k − 1
If r = 6then,
r3 = 216 = 217 − 1 = 31⋅7 − 1, so n3 = 7k + 1
Thus, the cube of any integer is of the form 7k, 7k+1 or 7k−1
Page 19 Problem 7 Answer
Obtain the following version of the Division Algorithm: For integers a and b, with b ≠ 0, there exist unique integers q and r that satisfy a = qb + r, where \(-\frac{1}{2}|b|<r \leq \frac{1}{2}|b|\).
It is required to obtain a following version of Division Algorithm: For integers a and b, with b≠0, there exists unique integers q and r that satisfy a = qb + r, where \(-\frac{1}{2}|b|<r \leq \frac{1}{2}|b|\).
The division algorithm for integers states that given any two integers a and b with b > 0, there exists unlque integers q and r such that a = qb + r, where 0 ≤ r < b.
Therefore, according to the division algorithm, there exists unique integers q′ and r′ such that a = q′b + r′, where 0 ≤ r′ < ∣b∣. Consider 0 < ∣b∣, this can be further divided into intervals, 0 < \(\frac{1}{2}|b|\) and \(\frac{1}{2}|b|\) < ∣b∣
Now, if 0 ≤ r’ ≤ \(\frac{1}{2}|b|\), let r = r’ and q = q’, and if \(\frac{1}{2}|b|\) < r’ < |b|, then \(-\frac{1}{2}|b|\) < r’ – |b| < 0, this gives,
a = q’b + r’ – |b| + |b|
If |b| ≥ 0, then |b| = b, that is,
a = q’b + r’ – |b| + b
This gives,
a = (q′+1)b + r′ − ∣b∣, therefore, let q = q′ + 1 and r = r′ − ∣b∣
If ∣b∣ < 0, then ∣b∣ = −b, that is,
a = q′b + r′ − ∣b∣ − b
This gives, a = (q′−1)b + r′ − ∣b∣, therefore, let q = q′ − 1 and r = r′ − ∣b∣
Therefore, if
\(\frac{1}{2}|b|\) < r’ < |b| = |b| – \(\frac{1}{2}|b|\) < r’ < |b| ⇒ \(-\frac{1}{2}|b|\) < r’ < 0 ⇒ \(-\frac{1}{2}|b|\) < r’ < 0 < \(\frac{1}{2}|b|\),
that is,
\(-\frac{1}{2}|b|<r^*<\frac{1}{2}|b|, \text { letr }=r^{\prime}-|b| a n d q=q^{\prime}+\frac{|b|}{b}\)Hence, for integers a and b. with b ≠ 0, there exists unique integers q and r that satisfy a = qb + r, where \(-\frac{1}{2}|b|<r \leq \frac{1}{2}|b|\).
Page 19 Problem 8 Answer
Here, we have to prove that no integer in the following sequence is a perfect square: 11,111,1111,11111,…
It’s given that a typical term 111⋅⋅⋅⋅⋅111 can be written as
111⋯111 = 111⋯108 + 3 = 4k + 3
Proof: Any number in sequence can be written as
A = 11 + 100 + 1000 + ….. = 11 + \(\sum_{i=2}^n 10^i\)
Each term of \(\sum_{i=2}^n 10^i\) is divisible by 4. So,
Ai= 11 + 4ri = 4(r+2) + 3, for certain ri
So, Ai = rr’i + 3 by division algorithm, r’ and 3 are unique. Suppose Ai = s2 let s = 4q + r
r ≠ 0,as
s2 = 16q2 = 4(4q2),which is not of the form 4ri′ + 3
r ≠ 1,as
s2 = 16q2 + 8q + 1 = 4(4q2+2q) + 1,which is not of the form 4ri′ + 3
r ≠ 2,as
s2 = 16q2 + 16q + 4 = 4(4q2 + 4q + 1),which is not of the form 4ri′ + 3
r ≠ 3,as
s2 = 16q2 + 24q + 9 = 4(4q2 + 2q + 2) + 1,which is not of the form 4ri′ + 3
Therefore there is no s such that s2 = 4ri + 3. All Ai are not perfect squares
Thus, we proved that no integer in the following sequence is a perfect square, 11,111,1111,11111,…
Page 19 Problem 9 Answer
Here, we have to verify that if an integer is simultaneously a square and a cube (as is the case with 64 = 82 = 43),then it must be either of the form 7k or 7k+1
Proof : By division algorithm, ∃s and k such that s = 7k + b,0 ≤ b < 7.Consider s3 = (7k+b)3, from binomial expansion, each term is a factor of 7 except last term,
(7k+b)3 = \(\left(\begin{array}{c}
3 \\
0
\end{array}\right)(7 k)^3+\left(\begin{array}{c}
3 \\
1
\end{array}\right)(7 k)^3 b+\left(\begin{array}{c}
3 \\
2
\end{array}\right)(7 k)^2 b^2+b^3\)
If b = 0 then, b3 = 0, and n3 = 7k as all other terms have 7 as a factor.
If b = 1 then, b3 = 1,then clearly n3 = 7k + 1
If b = 2 then,
b3 = 8 = 7 + 1,so n3 = 7k + 1
If b = 3 then,
b3 = 27 = 28 − 1 = 4⋅7 − 1, so n3 = 7k − 1
If b = 4 then,
b3 = 64 = 63 + 1 = 9⋅7 + 1, and n3 = 7k + 1
If b = 5 then,
b3 = 125 = 126 − 1 = 18⋅7 − 1, so n3 = 7k − 1
If b = 6 then,
b3 = 216 = 217 − 1 = 31⋅7−1, so n3 = 7k + 1
Now by division algorithm, ∃r and c such that r = 7c + d,0 ≤ d < 7 then,
If d = 0 then,r2 = 7(7c2) = 7k
If d = 1 then,
r2 = 49c2 + 14c + 1 = 7(7c2+2c) + 1 = 7k + 1
If d = 2 then,
r2 = 49c2 + 28c + 4 = 7(7c2+4c) + 4 = 7k + 4
If d = 3 then,
r2 = 49c2 + 42c + 9 = 7(7c2+6c+1) + 2 = 7k + 2
If d = 4 then,
r2 = 49c2 + 56c + 16 = 7(7c2+8c+2) + 2 = 7k + 2
If d = 5 then,
r2 = 49c2 + 70c + 25 = 7(7c2+10c+3) + 4 = 7k + 4
If d = 6 then,
r2 = 49c2 + 84c + 36 = 7(7c2+12c+5) + 1 = 7k + 1
Thus r2 is of the form : 7k, 7k+1, 7k+2 or 7k+4 and s3 is of the form :7k, 7k+1 or 7k+6. By uniqueness part of division algorithm, A must be either of form 7k or 7k+1
Thus, we verify that if an integer is simultaneously a square and a cube (as is the case with 64 = 82 = 43),then it must be either of the form 7k or 7k+1
Page 19 Problem 10 Answer
Here, we have to establish that the integer n(7n2+5) is of the form 6k
By division algorithm n=6k+r, 0 ≤ r < 6
If n = 6k then,(6k)(7(36k2)+5) = 6t
If n = 6k + 1 then,
(6k+1)(7(6k+1)2+5) = (6k+1)(7(36k2+12k+1)+5) = 6(6k+ 1) (7(6k2+2k)+2) = 6t
If n = 6k + 2 then,
2(3k+1)(7(6k+2)2+5) = 2(3k+1)(7(36k2+24k+4)+5) = 6(3k+ 1) (7(12k2+8k)+11) = 6t
If n = 6k + 3 then,
3(2k+1)(7(6k+3)2+5) = 3(2k+1)(7(36k2+36k+9)+5) = 6(6k+ 1) (7(18k2+18k)+34) = 6t
If n = 6k + 4then,
2(3k+2)(7(6k+4)2+5) = 2(3k+2)(7(36k2+48k+16)+5) = 2(3k+ 2) (7(12k2+16k)+39) = 6t
If n = 6k + 5 then,
(6k+5)(7(6k+5)2+5) = (6k+5)(7(36k2+60k+25)+5) = (6k+5)(7(36k2+60k)+180) = 6(6k+5)(7(6k2+10k)+30) = 6t
Thus, in all cases we have n(7n2+5) is of the form 6k
Thus, we establish that the integer n(7n2+5) is of the form 6k
Page 19 Problem 11 Answer
Here, we have to show that n4 + 4n2 + 11 is of the form 16k
Since, n is odd then n = 2r + 1
n4 + 4n2 + 11 = (n2+2)2 + 7
= [(2r+1)2+2]2 + 7
= (4r2+4r+1+2)2 + 7
= (4r2+4r+3)2 + 7
= [(4r2+4r)+3]2 + 7
= (4r2+4r)2 + 2⋅(4r2+4r)⋅3 + 9 + 7
= 16r4 + 2⋅4r2⋅4r + 16r2 + 24r2 + 24r + 9 + 7
= 16r4 + 32r3 + 16r2 + 24r2 + 24r + 9 + 7
= 16r4 + 32r3 + 40r2 + 24r + 16
Now, by division algorithm, r = 2q or 2q + 1
If r = 2q:
16(2q)4 + 32(2q)3 + 40(2q)2 + 24(2q) + 16
= 16[(2q)4 + 2(2q)3 + 10q2 + 3q + 1]
= 16k
If r = 2q + 1:
16(2q+1)4 + 32(2q+1)3 + 40(2q+1)2 + 24(2q+1) + 16
= 16(2q+1)4 + 32(2q+1)3 + 160q2 + 160q + 40 + 48q + 24 + 16
= 16[(2q+1)4 + 2(2q+1)3 + 10q2 + 10q + 3q + 4 + 1]
= 16k
Thus, we showed that n4 + 4n2 + 11 is of the form 16k