David Burton Elementary Number Theory Solutions Chapter 2 Divisibility Theory In The Integers Exercise 2.2

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

David Burton Elementary Number Theory Chapter 2 Exercise 2.2 Solutions

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: ∴ a² = 9q² = 3(3q²) = 3k where k = 3q²

If a = 3q + 1: ∴ a² = 9q² + 6q + 1 = 3(3q²+2q) + 1 = 3k + 1 where k = 3q² + 2q

If a = 3q + 2: ∴ a² = 9q² + 12q + 4 = 9q² + 12q + 3 + 1 = 3(3q²+4q+1) + 1 = 3k+1 where k = 3q² + 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 n⁴ = (5q+r)⁴,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 r⁴ = 0, and n⁴ = 5k as all other terms have 5 as a factor

If r = 1 then r⁴ = 1,then clearly n⁴ = 5k + 1

If r = 2 then r⁴ = 16 = 15 + 1 = 3⋅5 + 1, so n⁴ = 5k + 1

If r = 3 then r⁴ = 81 = 80 + 1 = 5⋅16 + 1, so n⁴ = 5k + 1

If r = 4 then r⁴ = 256 = 255 + 1 = 5⋅51 + 1, so n⁴ = 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

Solutions To Chapter 2 Exercise 2.2 Burton Number Theory

David Burton Elementary Number Theory Solutions Chapter 2 Divisibility Theory In The Integers Exercise 2.2 Page 19 Problem 4 Answer

Here, we have to prove that 3a² − 1 is never a perfect square

Proof :

Suppose 3a² − 1 = n², some n by Ex3(a),

3a² − 1 = 3k + 1 or 3a^{2} − 1 = 3k

∴ 3(a²−k) = 2 or 3(a²−k) = 1,

but each are impossible, since by division algorithm, 2 = 3⋅0 + 2 and 1 = 3⋅0 + 1

Thus, we proved that 3a² − 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 n³ = (7q+r)³,from binomial expansion, each term is a factor of 7 except last term,

(7q+r)³ = \(\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, r³ = 0and n³ = 7k as all other terms have 7 as a factor.

If r = 1then, r³ = 1,then clearly n³ = 7k + 1

If r = 2then,

r³ = 8 = 7 + 1, so n³ = 7k + 1

If r = 3then,

r³ = 27 = 28 − 1 = 4⋅7 − 1, sо n³ = 7k − 1

If r = 4then,

r³ = 64 = 63 + 1 = 9⋅7 + 1, and n³ = 7k + 1

If r = 5then,

r³ = 125 = 126−1 = 18⋅7 − 1, so n³ = 7k − 1

If r = 6then,

r³ = 216 = 217 − 1 = 31⋅7 − 1, so n³ = 7k + 1

Thus, the cube of any integer is of the form 7k, 7k+1 or 7k−1

Divisibility Theory Exercise 2.2 Answers David Burton

David Burton Elementary Number Theory Solutions Chapter 2 Divisibility Theory In The Integers Exercise 2.2 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,

A_i= 11 + 4r_i = 4(r+2) + 3, for certain r_i

So, A_i = rr’_i + 3 by division algorithm, r’ and 3 are unique. Suppose A_i = s² let s = 4q + r

r ≠ 0,as

s² = 16q² = 4(4q²),which is not of the form 4r_i′ + 3

r ≠ 1,as

s² = 16q² + 8q + 1 = 4(4q²+2q) + 1,which is not of the form 4r_i′ + 3

r ≠ 2,as

s² = 16q² + 16q + 4 = 4(4q² + 4q + 1),which is not of the form 4r_i′ + 3

r ≠ 3,as

s² = 16q² + 24q + 9 = 4(4q² + 2q + 2) + 1,which is not of the form 4r_i′ + 3

Therefore there is no s such that s² = 4r_i + 3. All A_i are not perfect squares

Thus, we proved that no integer in the following sequence is a perfect square, 11,111,1111,11111,…

 

David Burton Elementary Number Theory Solutions Chapter 2 Divisibility Theory In The Integers Exercise 2.2 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 = 8² = 4³),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 s³ = (7k+b)³, from binomial expansion, each term is a factor of 7 except last term,

(7k+b)³ = \(\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, b³ = 0, and n³ = 7k as all other terms have 7 as a factor.

If b = 1 then, b³ = 1,then clearly n³ = 7k + 1

If b = 2 then,

b³ = 8 = 7 + 1,so n³ = 7k + 1

If b = 3 then,

b³ = 27 = 28 − 1 = 4⋅7 − 1, so n³ = 7k − 1

If b = 4 then,

b³ = 64 = 63 + 1 = 9⋅7 + 1, and n³ = 7k + 1

If b = 5 then,

b³ = 125 = 126 − 1 = 18⋅7 − 1, so n³ = 7k − 1

If b = 6 then,

b³ = 216 = 217 − 1 = 31⋅7−1, so n³ = 7k + 1

Now by division algorithm, ∃r and c such that r = 7c + d,0 ≤ d < 7 then,

If d = 0 then,r² = 7(7c²) = 7k

If d = 1 then,

r² = 49c² + 14c + 1 = 7(7c²+2c) + 1 = 7k + 1

If d = 2 then,

r² = 49c² + 28c + 4 = 7(7c²+4c) + 4 = 7k + 4

If d = 3 then,

r² = 49c² + 42c + 9 = 7(7c²+6c+1) + 2 = 7k + 2

If d = 4 then,

r² = 49c² + 56c + 16 = 7(7c²+8c+2) + 2 = 7k + 2

If d = 5 then,

r² = 49c² + 70c + 25 = 7(7c²+10c+3) + 4 = 7k + 4

If d = 6 then,

r² = 49c² + 84c + 36 = 7(7c²+12c+5) + 1 = 7k + 1

Thus r² is of the form : 7k, 7k+1, 7k+2 or 7k+4 and s³ 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 = 8² = 4³),then it must be either of the form 7k or 7k+1

How To Solve Chapter 2 Exercise 2.2 Burton Number Theory

Page 19 Problem 10 Answer

Here, we have to establish that the integer n(7n²+5) is of the form 6k

By division algorithm n=6k+r, 0 ≤ r < 6

If n = 6k then,(6k)(7(36k²)+5) = 6t

If n = 6k + 1 then,

(6k+1)(7(6k+1)²+5) = (6k+1)(7(36k²+12k+1)+5) = 6(6k+ 1) (7(6k²+2k)+2) = 6t

If n = 6k + 2 then,

2(3k+1)(7(6k+2)²+5) = 2(3k+1)(7(36k²+24k+4)+5) = 6(3k+ 1) (7(12k²+8k)+11) = 6t

If n = 6k + 3 then,

3(2k+1)(7(6k+3)²+5) = 3(2k+1)(7(36k²+36k+9)+5) = 6(6k+ 1) (7(18k²+18k)+34) = 6t

If n = 6k + 4then,

2(3k+2)(7(6k+4)²+5) = 2(3k+2)(7(36k²+48k+16)+5) = 2(3k+ 2) (7(12k²+16k)+39) = 6t

If n = 6k + 5 then,

(6k+5)(7(6k+5)²+5) = (6k+5)(7(36k²+60k+25)+5) = (6k+5)(7(36k²+60k)+180) = 6(6k+5)(7(6k²+10k)+30) = 6t

Thus, in all cases we have n(7n²+5) is of the form 6k

Thus, we establish that the integer n(7n²+5) is of the form 6k

Elementary Number Theory Burton Chapter 2 Exercise 2.2 Explanations

David Burton Elementary Number Theory Solutions Chapter 2 Divisibility Theory In The Integers Exercise 2.2 Page 19 Problem 11 Answer

Here, we have to show that n⁴ + 4n² + 11 is of the form 16k

Since, n is odd then n = 2r + 1

n⁴ + 4n² + 11 = (n²+2)² + 7

= [(2r+1)²+2]² + 7

= (4r²+4r+1+2)² + 7

= (4r²+4r+3)² + 7

= [(4r²+4r)+3]² + 7

= (4r²+4r)² + 2⋅(4r²+4r)⋅3 + 9 + 7

= 16r⁴ + 2⋅4r²⋅4r + 16r² + 24r² + 24r + 9 + 7

= 16r⁴ + 32r³ + 16r² + 24r² + 24r + 9 + 7

= 16r⁴ + 32r³ + 40r² + 24r + 16

Now, by division algorithm, r = 2q or 2q + 1

If r = 2q: ​

​16(2q)⁴ + 32(2q)³ + 40(2q)² + 24(2q) + 16

= 16[(2q)⁴ + 2(2q)³ + 10q² + 3q + 1]

= 16k

If r = 2q + 1:​

​16(2q+1)⁴ + 32(2q+1)³ + 40(2q+1)² + 24(2q+1) + 16

= 16(2q+1)⁴ + 32(2q+1)³ + 160q² + 160q + 40 + 48q + 24 + 16

= 16[(2q+1)⁴ + 2(2q+1)³ + 10q² + 10q + 3q + 4 + 1]

= 16k

Thus, we showed that n⁴ + 4n² + 11 is of the form 16k