## 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: ∴ a^{2} = 9q^{2 }= 3(3q^{2}) = 3k where k = 3q^{2}

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

If a = 3q + 2: ∴ a^{2} = 9q^{2} + 12q + 4 = 9q^{2} + 12q + 3 + 1 = 3(3q^{2}+4q+1) + 1 = 3k+1 where k = 3q^{2} + 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^{4} = (5q+r)^{4},from binomial expansion, each term is a factor of 5 except last term.

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^{4} = 0, and n^{4} = 5k as all other terms have 5 as a factor

If r = 1 then r^{4} = 1,then clearly n^{4} = 5k + 1

If r = 2 then r^{4} = 16 = 15 + 1 = 3⋅5 + 1, so n^{4} = 5k + 1

If r = 3 then r^{4} = 81 = 80 + 1 = 5⋅16 + 1, so n^{4} = 5k + 1

If r = 4 then r^{4} = 256 = 255 + 1 = 5⋅51 + 1, so n^{4} = 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 3a^{2} − 1 is never a perfect square

**Proof :**

Suppose 3a^{2} − 1 = n^{2}, some n by Ex3(a),

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

∴ 3(a^{2}−k) = 2 or 3(a^{2}−k) = 1,

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

Thus, we proved that 3a^{2} − 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^{3} = (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, r^{3} = 0and n^{3} = 7k as all other terms have 7 as a factor.

If r = 1then, r^{3} = 1,then clearly n^{3} = 7k + 1

If r = 2then,

r^{3} = 8 = 7 + 1, so n^{3} = 7k + 1

If r = 3then,

r^{3} = 27 = 28 − 1 = 4⋅7 − 1, sо n^{3} = 7k − 1

If r = 4then,

r^{3} = 64 = 63 + 1 = 9⋅7 + 1, and n^{3} = 7k + 1

If r = 5then,

r^{3} = 125 = 126−1 = 18⋅7 − 1, so n^{3} = 7k − 1

If r = 6then,

r^{3} = 216 = 217 − 1 = 31⋅7 − 1, so n^{3} = 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,

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^{2} let s = 4q + r

r ≠ 0,as

s^{2} = 16q^{2} = 4(4q^{2}),which is not of the form 4r_{i}′ + 3

r ≠ 1,as

s^{2} = 16q^{2} + 8q + 1 = 4(4q^{2}+2q) + 1,which is not of the form 4r_{i}′ + 3

r ≠ 2,as

s^{2} = 16q^{2 }+ 16q + 4 = 4(4q^{2} + 4q + 1),which is not of the form 4r_{i}′ + 3

r ≠ 3,as

s^{2} = 16q^{2} + 24q + 9 = 4(4q^{2} + 2q + 2) + 1,which is not of the form 4r_{i}′ + 3

Therefore there is no s such that s^{2} = 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,…

**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^{2} = 4^{3}),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^{3} = (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, b^{3} = 0, and n^{3} = 7k as all other terms have 7 as a factor.

If b = 1 then, b^{3} = 1,then clearly n^{3} = 7k + 1

If b = 2 then,

b^{3} = 8 = 7 + 1,so n^{3} = 7k + 1

If b = 3 then,

b^{3} = 27 = 28 − 1 = 4⋅7 − 1, so n^{3} = 7k − 1

If b = 4 then,

b^{3} = 64 = 63 + 1 = 9⋅7 + 1, and n^{3} = 7k + 1

If b = 5 then,

b^{3} = 125 = 126 − 1 = 18⋅7 − 1, so n^{3} = 7k − 1

If b = 6 then,

b^{3} = 216 = 217 − 1 = 31⋅7−1, so n^{3} = 7k + 1

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

If d = 0 then,r^{2} = 7(7c^{2}) = 7k

If d = 1 then,

r^{2} = 49c^{2} + 14c + 1 = 7(7c^{2}+2c) + 1 = 7k + 1

If d = 2 then,

r^{2} = 49c^{2} + 28c + 4 = 7(7c^{2}+4c) + 4 = 7k + 4

If d = 3 then,

r^{2} = 49c^{2} + 42c + 9 = 7(7c^{2}+6c+1) + 2 = 7k + 2

If d = 4 then,

r^{2} = 49c^{2} + 56c + 16 = 7(7c^{2}+8c+2) + 2 = 7k + 2

If d = 5 then,

r^{2} = 49c^{2} + 70c + 25 = 7(7c^{2}+10c+3) + 4 = 7k + 4

If d = 6 then,

r^{2} = 49c^{2} + 84c + 36 = 7(7c^{2}+12c+5) + 1 = 7k + 1

Thus r^{2} is of the form : 7k, 7k+1, 7k+2 or 7k+4 and s^{3} 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^{2} = 4^{3}),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(7n^{2}+5) is of the form 6k

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

If n = 6k then,(6k)(7(36k^{2})+5) = 6t

If n = 6k + 1 then,

(6k+1)(7(6k+1)^{2}+5) = (6k+1)(7(36k^{2}+12k+1)+5) = 6(6k+ 1) (7(6k^{2}+2k)+2) = 6t

If n = 6k + 2 then,

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

If n = 6k + 3 then,

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

If n = 6k + 4then,

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

If n = 6k + 5 then,

(6k+5)(7(6k+5)^{2}+5) = (6k+5)(7(36k^{2}+60k+25)+5) = (6k+5)(7(36k^{2}+60k)+180) = 6(6k+5)(7(6k^{2}+10k)+30) = 6t

Thus, in all cases we have n(7n^{2}+5) is of the form 6k

Thus, we establish that the integer n(7n^{2}+5) is of the form 6k

**Page 19 Problem 11 Answer**

Here, we have to show that n^{4} + 4n^{2} + 11 is of the form 16k

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

n^{4} + 4n^{2} + 11 = (n^{2}+2)^{2} + 7

= [(2r+1)^{2}+2]^{2} + 7

= (4r^{2}+4r+1+2)^{2} + 7

= (4r^{2}+4r+3)^{2} + 7

= [(4r^{2}+4r)+3]^{2} + 7

= (4r^{2}+4r)^{2} + 2⋅(4r^{2}+4r)⋅3 + 9 + 7

= 16r^{4} + 2⋅4r^{2}⋅4r + 16r^{2} + 24r^{2} + 24r + 9 + 7

= 16r^{4} + 32r^{3} + 16r^{2} + 24r^{2} + 24r + 9 + 7

= 16r^{4} + 32r^{3} + 40r^{2} + 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} + 10q^{2} + 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} + 160q^{2} + 160q + 40 + 48q + 24 + 16

= 16[(2q+1)^{4} + 2(2q+1)^{3} + 10q^{2} + 10q + 3q + 4 + 1]

= 16k

Thus, we showed that n^{4} + 4n^{2} + 11 is of the form 16k