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

**Page 24 Problem 1 Answer**

Here ,we have to show that (-a)|b, a|(-b), and (-a)|(-b)

Let a∣b then ∃ c ∋ a⋅c = b

⟹ a⋅c = (−a)⋅(−c) = b ⟹ (−a)∣b

⟹ −(a⋅c) = −b = a⋅(−c) ⟹ a∣(−b)

⟹ −(a⋅c) = −b = (−a)⋅c ⇒ (−a)∣(−b)

Thus, we show that (−a)∣b, a∣(−b), and (−a)∣(−b).

**Page 24 Problem 2 Answer**

Here, we have to verify that if a∣b then a∣bc

Let a∣b then ∃x ∋ a⋅x = b

∴ ac = bc ⟹ a ∣ bc

Thus, we verified that if a ∣ b, then a ∣ bc

Here, we have to verify that if a∣b and a∣c then a^{2}∣ bc

Let a∣b and a∣c then, ∃ x,y ∋ ax = b,ay = c

∴ (ax)(ay) = bc = a^{2}xy ⟹ a^{2} ∣ bc

Thus, we verified that if a∣b and a∣c, then a^{2} ∣ bc

Here, we have to verify that a∣b if and only if ac ∣ bc, where c ≠ 0

Let a∣b then ∃ x ∋ ax = b,

∴ acx = bc = a^{2}xy ⟹ ac ∣ bc

Now, let ac ∣ bc then ∃ x ∋ acx = bc

Since, c ≠ 0 ∴ ax = b ⟹ a ∣ b

Thus, we verified that a∣b if and only if ac ∣ bc, where c ≠ 0

Here, we have to verify that if a ∣ b and c ∣ d, then ac ∣ bd

Let a∣b and c∣d then, ∃ x, y ∋ ax = b,cy = d

∴ (ax)(cy) = ac(xy) = bd ⟹ ac ∣ bd.

Thus, we verified that a ∣ b and c ∣ d then, ac ∣ bd

**Page 24 Problem 4 Answer**

Here, we have to use mathematical induction to establish the divisibility statements, 8∣52n + 7.It’s given that 5^{2(k+1)} + 7 = 5^{2}(5^{2k}+7) + (7−5^{2}⋅7).

For n = 1:5^{2n} + 7 = 25 + 7 = 32 and 8 ∣ 32.Suppose it’s true for n = k then we want to prove it for n = k + 1.

Let 8 ∣ 5^{2k} + 7 ∴ ∃ x ∋ 8x = 5^{2k} + 7

Now, for n = k + 1

5^{2(k+1)} + 7 = 5^{2}⋅5^{2k} + 7

= 5^{2}(5^{2k}+7) − 5^{2}⋅7 + 7

= 5^{2}(8x) − 5^{2} − 7(5^{2}−1)

= 5^{2}(8x) − 7(24)

= 8x(25) − 8(7⋅3)

= 8(25x−21)

∴ 8 ∣ 5^{k+1}

Thus, by mathematical induction for n ≥ 1,8 ∣ 5^{n}

Thus, we have to use mathematical induction to establish the divisibility statements 8 ∣ 5^{2n} + 7

Here, we have to use mathematical induction to establish the divisibility statements, 15 ∣ 2^{4n} − 1

For, n = 1 : 2^{4} − 1 = 16 − 1 = 15 and 15 ∣ 15.Suppose it’s true for n = k then we want to prove it for n = k + 1.

Let 15 ∣ (2^{4k}−1) ∴ ∃ x ∋ 15x = 2^{4k} − 1

Now, for n = k + 1

2^{4(k+1)} − 1 = 2^{4}⋅2^{4k} − 1 + 2^{4} − 2^{4}

= 2^{4}(2^{4k}−1) + (2^{4}−1)

= 2^{4}(15x) + 15

= 15(x2^{4}+1)

∴ 15 ∣ 2^{4(k+1)} − 1

Thus, by mathematical induction for n ≥ 1,15 ∣ 2^{4n} − 1

Thus, we use mathematical induction to establish the divisibility statements, 15 ∣ 2^{4n} − 1

Here, we have to use mathematical induction to establish the divisibility statements, 5 ∣ 3^{3n+1} + 2^{n+1}

For n = 1 : 3^{3+1} + 2^{2} = 81 + 4 = 85 and 5 ∣ 85. Suppose it’s true for n = k then we want to prove it for n=k+1.

Let 5 ∣(3^{3k+1} + 2^{k+1}) ∴ ∃ x ∋ 5x = 3^{3k+1} + 2^{k+1}

Now for n = k + 1

3^{3(k+1)+1} − 2^{k+2} = 3^{3k+4} − 2^{k+2}

= 3^{3}⋅3^{3k+1} + 2⋅2^{k+1 }+ 3⋅2^{k+1} − 3^{3}⋅2^{k+1}

= 3^{3}(3^{3k+1} + 2^{k+1}) − 2^{k+1}(3^{3}−2)

= 3^{3}(5x) − 2^{k+1}(25)

= 5(x3^{3} − 5⋅2^{k+1})

∴ 5 ∣ (3^{3n+1} + 2^{n+1})

Thus, by mathematical induction for n ≥ 1, 5 ∣ 2^{4n} − 1

Thus, we use mathematical induction to establish the divisibility statements, 5 ∣ 2^{4n}−1

Here, we have to use mathematical induction to establish the divisibility statements, 21 ∣ 4^{n+1} + 5^{2n-1}

For ,n = 1: 4^{2} + 5^{1} = 21 and 21 ∣ 21.Suppose, it’s true for n = k then we want to prove it for n = k + 1.

Let 21 ∣ (4^{k+1}+5^{2k-1}) ∴ ∃ x ∋ 21x = 4^{k+1} + 5^{2k-1}

Now, for n = k + 1

4^{3(k+2)} − 5^{2(k+1)}−1 = 4^{k+2 }− 5^{2k+1}

= 4⋅4^{k+1} + 5^{2}⋅5^{2k-1} + 4⋅5^{2k-1}− 4⋅5^{2k-1}

= 4(4^{k+1} + 5^{2k-1}) + 21(5^{2k-1})

= 4(21x) + 21(5^{2k-1})

= 21(4x+5^{2k-1})

∴ 21 ∣ (4^{(k+1)+1} + 5^{2(k+1)-1})

Thus, by mathematical induction for n ≥ 1, 21∣(4^{k+1 }+ 5^{2k+1})

Thus, we use mathematical induction to establish the divisibility statements, 21 ∣ 4^{n+1} + 5^{2n-1}

Here, we have to use mathematical induction to establish the divisibility statements, 24 ∣ 2⋅7^{n} + 3⋅5^{n}−5

Now we want to prove by mathematical induction that 24 ∣ 4⋅7^{k} + 20 for s = 1: 4⋅7^{1} + 20 = 48 and 24 ∣ 48

Suppose it’s true for k = s then we want to prove it for k=s+1

Let 24 ∣ 4⋅7^{s} + 20 ∴ ∃ x ∋ 24x = 4⋅7^{s} + 20

Now, for n = k + 1

4⋅7^{s}+1 + 20 = 7(4⋅7^{s})+20

= 7(4⋅7^{s}+20) + 20 − 140

= 7(24y) − 24⋅5

∴ ∃ q ∋ 24q = 4⋅7^{k} + 20

∴ eq (1) = 5(24x) + 24q

Thus, by mathematical induction for n ≥ 1,24 ∣ 2⋅7^{n} + 3⋅5^{n}−5

Thus, we use mathematical induction to establish the divisibility statements, 24 ∣ 2⋅7^{n} + 3⋅5^{n}−5

**Page 24 Problem 5 Answer**

Here, we have to prove that for any integer a one of the integers a,a+2,a+4 is divisible by 3

From the division algorithm, we know that every a is on the form 3q, 3q+1 or 3q+2

Case 1: Suppose a = 3q, then a is divisible by 3

Case 2: Suppose a = 3q + 1,then a + 4 = 3q + 6 = 3(q+2),then a+2 is divisible by 3

Case 3: Suppose a = 3q + 2,then a+4 = 3q + 6 = 3(q+2).Thus a+1 is divisible by 3

therefore for any integer a,any of the forms a,a+2 or a+4 is divisible by 3

Thus, we prove that for any integer a one of the integers a, a+2, a+4 is divisible by 3

**Page 25 Problem 6 Answer**

Here, we have to verify that 2∣a(a+1), and 3∣a(a+1)(a+2)

According to the division algorithm, every a is of the form 2q or 2q+1

Case 1: If a = 2q then a + 1 = 2q + 1, since a is even ⟹ 2∣a ⟹ 2∣a(a+1)

Case 2 : If a = 2q + 1 then

a + 1 = 2q + 2 = 2(q+1), since a + 1 is even ⟹ 2∣a+1 ⟹ 2∣a(a+1)

According to division algorithm, every a is of the form 3q,3q+1 or 3q+2

Case 1 : If a = 3q then

3∣a ⟹ 3∣a(a+1)(a+2)

Case 2 : If a = 3q + 1 then,

a + 2 = 3q + 3 = 3(q+1),thus

3 ∣a + 2 ⟹ 3∣a(a+1)(a+2)

Case 3: If a = 3q + 2,then

a + 1 = 3q + 3 = 3(q+1),thus

3∣a + 1 ⟹ 3∣a(a+1)(a+2)

Thus, we verify that 2∣a(a+1), and 3∣a(a+1)(a+2).

Here, we have to verify that 3∣a(2a^{2}+7)

According to the division algorithm, every a is of the form, 3q,3q+1, or 3q+2

Case 1 : If a = 3q then,3 ∣ a ⟹ 3∣a(2a^{2}+7)

Case 2: If a = 3q + 1 then, a^{2} = 9q^{2} + 6q + 1,

⟹ 2a^{2} + 7 = 2(9q^{2}+6q+1) + 7

= 18q^{2} + 12q + 9 = 3(6q^{2}+4q+3)

thus 3∣∣2a^{2} + 7 ⟹ 3∣∣a(2a^{2}+7)

Case 3: If a = 3q + 2 then, a^{2} = 9q^{2} + 12q + 4,

⟹ 2a^{2} + 7 = 2(9q^{2}+12q+4) + 7

= 18q^{2} + 24q + 15 = 3(6q^{2}+8q+5)

Thus 3 ∣ 2a^{2} + 7 ⟹ 3 ∣ a(2a^{2}+7)

Thus, we verified 3 ∣ a(2a^{2}+7)

Here, we have to verify that if a is odd ,then 32 ∣ (a^{2}+3)(a^{2}+7)

According to the division algorithm, every a is in the form 4q + r ∋ 0 ≤ r ≤ 3. But a is odd then the only possible forms of a are 4q+1 or 4q+3

Case 1 : If a = 4q + 1, then a^{2} = 16q^{2} + 8q + 1

⟹ a^{2} + 3 = 16q^{2} + 8q + 4 = 4(4q^{2}+2q+1)⋯(1)

a^{2} + 7 = 16q^{2} + 8q + 8 = 8(2q^{2}+q+1)⋯(2)

From (1) and (2)

(a^{2}+3)(a^{2}+7) = [4(4q^{2}+2q+1)][8(2q^{2}+q+1)]

= 32(4q^{2}+2q+1)(2q^{2}+q+1)

Thus 32 ∣ (a^{2}+3)(a^{2}+7)

Case 2 : If a a = 4q + 3 then,

a^{2} = 16q^{2} + 24q + 9

⟹ a^{2} + 3 = 16q^{2} + 24q + 12 = 4(4q^{2}+6q+3)⋯(1)

a^{2} + 7 = 16q^{2} + 24q + 16 = 8(2q^{2}+3q+2)⋯(2)

from (1) and (2)

(a^{2}+3)(a^{2}+7) = [4(4q^{2}+6q+3)][8(2q^{2}+3q+2)]

= 32(4q^{2}+6q+3)(2q^{2}+3q+2)

Thus 32 ∣ (a^{2}+3)(a^{2}+7)

Thus, we verified if a is odd ,then 32∣(a^{2}+3)(a^{2}+7)

**Page 25 Problem 7 Answer**

Here, we have to prove that if a and b are both odd integers, then 16 ∣ a^{4} + b^{4} − 2

Since a and b are both odd integers then a = 2r + 1 and b = 2s + 1 where k, l ∈ Z.

Now,

a^{4} + b^{4} – 2 = (2r+1)^{4} + (2s+1)^{4} – 2

= \(\left(\begin{array}{l}

4 \\

0

\end{array}\right)(2 r)^4+\left(\begin{array}{l}

4 \\

1

\end{array}\right)(2 r)^3+\left(\begin{array}{l}

4 \\

2

\end{array}\right)(2 r)^2+\left(\begin{array}{l}

4 \\

3

\end{array}\right)(2 r)+1\)

+\(\left(\begin{array}{l}

4 \\

0

\end{array}\right)(2 s)^4+\left(\begin{array}{l}

4 \\

1

\end{array}\right)(2 s)^3+\left(\begin{array}{l}

4 \\

2

\end{array}\right)(2 s)^2+\left(\begin{array}{l}

4 \\

3

\end{array}\right)(2 s)+1-2\)

= 16(r^{4}+s^{4}) + 32(r^{3}+s^{3}) + 24r^{2} + 8r + 24s^{2} + 8s

to prove that 16 ∣ a^{4} + b^{4} − 2 we just need 16 ∣ 24r^{2} + 8r

If r is odd then r = 2k + 1,then

24(2k+1)^{2} + 8(2k+1)

= 96k^{2} + 96k + 24 + 16k + 8

= 96k^{2} + 96k + 16k + 32

= 16(8k^{2}+8k+k+2)

If r is even then r = 2k,thus

24(2k)^{2} + 8(2k) = 96k^{2} + 16k = 16(8k^{2}+k)

Thus, 16 ∣ 24r^{2} + 8r, similarly 16 ∣ 24s^{2} + 8s

∴ 16 ∣ a^{4} + b^{4} − 2

Thus, we prove that if a and b are both odd integers, then 16 ∣ a^{4} + b^{4} − 2

**Page 25 Problem 8 Answer**

Here, we have to prove that the sum of the squares of two odd integers cannot be a perfect square.

Let a and b be odd integers, then a = 2r + 1 and b = 2s + 1 for some r, s ∈ Z.

Now,

a^{2} + b^{2} = (2r+1)^{2} + (2s+1)^{2} = 4r^{2} + 4r + 1 + 4s^{2} + 4s + 1 = 4(r^{2}+s^{2}+r+s) + 2 = 4k + 2

where, k = r^{2} + s^{2} + r + s

Suppose a^{2 }+ b^{2} is a perfect square, then a^{2} + b^{2 }= c^{2} = 4k + 2 = 2(2k+1)

Then c^{2} is even ⇒ c is even, so c = 2m ⟹ c^{2} = 4m^{2} = 4l where l = m^{2}

Thus, a^{2} + b^{2} = c^{2} ⟹ 4k + 2 = 4l,this contradict the uniqueness of division algorithm, ∴ a^{2} + b^{2} ≠ c^{2} if a, b are odd

Thus, we proved that the sum of the squares of two odd integers cannot be a perfect square.

We have to prove that the product of four consecutive integers is 1 less than a perfect square.

Consider the four consecutive integers be k, k+1, k+2 and k+3

The product of these integers will be,

k(k+3)(k+1)(k+2) = (k^{2}+3k)(k^{2}+3k+2)

=((k^{2}+3k+1)−1)((k^{2}+3k+1)+1)

= (k^{2}+3k+1)^{2} − 12

Now let(k^{2}+3k+1) = p where p is some integer.

Hence (k^{2}+3k+1)^{2} = p^{2}

Therefore we have,

k(k+3)(k+1)(k+2) = p^{2} − 1

Hence we have proved that the product of four consecutive integers is 1 less than a perfect square.

**Page 25 Problem 9 Answer**

We have to establish that the difference of two consecutive cubes is never divisible by 2.

Consider the two consecutive numbers be a and a+1

Here ∤ symbolize does not divide and ∣ means does divide.

We have to prove 2 ∤ (a+1)^{3} − a^{3}

Solving (a+1)^{3} − a^{3} we get,

(a+1)^{3} − a^{3} = a^{3} + 3a^{2} + 3a + 1 − a^{3}

= 3a^{2} + 3a + 1

= 3a(a+1) + 1

Now,

if a is even then,

2 ∣ a

⇒ 2 ∣ a(a+1)

if a is odd, then a+1 is even, then,

2 ∣ a + 1

⇒ 2 ∣ a(a+1)

So 2 ∣ a(a+1)

Therefore,

x ∈ Z, 2x = a(a+1)

Thus,

3a(a+1) + 1 = 3(2x)+1

= 2(3x) + 1

which is odd.

Hence 2∤(a+1)^{3} − a^{3}.

Hence we have proved that 2 ∤ (a+1)^{3} − a^{3}.

**Page 25 Problem 10 Answer**

We have to show that

gcd(a,0) = ∣a∣

gcd(a,a) = ∣a∣

gcd(a,1) = 1

Sincea∣0 and a∣a,then ∣a∣ is a common divisor of a and 0.

Now, let b be another common divisor of a,0.

Then,

b ∣ a

⇒ ∣b∣ ≤ ∣a∣

Thus ∣a∣ is the greatest common divisor of a and 0.

Since a∣a, then ∣a∣ is a common divisor of a. Now, let b be another common divisor of a and a.

Then,

b ∣ a

⇒ ∣b∣ ≤ ∣a∣

Thus ∣a∣ is the greatest common divisor of a and a.

Since 1∣a and 1∣1,then 1 is a common divisor of a and 1.

Now, let b be another common divisor of a,1.

Then,

b ∣ 1

⇒ ∣b∣ ≤ 1

Thus 1 is the greatest common divisor of a and 1.

Hence we have proved that,

gcd(a,0) = ∣a∣

gcd(a,a) = ∣a∣

gcd(a,1) = 1

**Page 25 Problem 12 Answer**

We have to prove that, for a positive integer n and any integer a, gcd(a,a+n) divides n and hence,gcd(a,a+1) = 1

Here a|b means a divides b

Let gcd(a,a+1) = d, then d|a and d|a+n

But we know that gcd(a, a+n) divides any linear combination of a and a+n.

Thus

d|(a+n) – a

⇒ d|n

Now, let gcd(a, a+1) = t

Therefore,

t|a + 1 – a

⇒ t|a

⇒ t ≤ 1

⇒ t = 1

Hence we have proved that for a positive integer n and any integer a,gcd(a,a+n) divides n and hence,gcd(a,a+1) = 1

**Page 25 Problem 13 Answer**

We are given integers a and b.

We have to prove that there exist integers x and y for which c = ax + by if and only ifgcd(a,b)∣c.

Let us assume c = ax + by,

Now let gcd(a,b) = d,

then d∣a and d∣b

thus there exists,

t,l in Z

a = dt

b = dl

Therefore,

c = ax + by

= dtx + dly

= d(tx+ly)

d∣c

Hence we have proved that there exist integers x and y for which c = ax + by if and only if gcd(a,b)∣c.

Given: Integers a and b, we have to prove:

If there exists integers x and y for which ax + by = gcd(a,b), then gcd(x,y) = 1

Let us assume gcd(a,b)∣c and let gcd(a,b) = d.

This implies c = fd for some f∈Z.

Then, ∃ s,r ∈ Z∋.

d = sa + rb

This implies:

c = fd

= f(sa+rb)

= (fs)a + (fr)b

= xa + yb

Where, x = fs

y = fr

Proved that if there exists integers x and y for which ax + by = gcd(a,b), then gcd(x,y) = 1.

**Page 25 Problem 15 Answer**

We are given thata and b are integers, not both of which are zero.

We have to prove that gcd(2a−3b,4a−5b) divides b and hence,gcd(2a+3,4a+5) = 1

We have,

−2(2a−3b) + (4a−5b) = −4a + 6b + 4a − 5b

−2(2a−3b) + (4a−5b) = b

Thus gcd(2a−3b,4a−5b) ∣ b.

Since 2(2a+3)−(4a+5) = 4a + 6 − 4a − 5

= 1

Thus gcd(2a+3,4a+5) ∣ 1 ⟹ gcd(2a+3,4a+5) = 1

Hence we have proved that gcd(2a−3b,4a−5b) divides b and hence,gcd(2a+3,4a+5) = 1

**Page 25 Problem 17 Answer**

We have to prove that the expression(3n)!/(3!)^{2} is an integer for all n ≥ 0.

For n = 1, we have,

\(\frac{(3 \cdot 1) !}{(3 !)^1}=\frac{6}{6}\)Hence the result is true for n = 1

Now let us assume that the result is true for n = k we have,

\(\frac{(3 \cdot 1) !}{(3 !)^1}\) = l, l is any integer

Now we have to prove that the result is true for n = k + 1

we have,

\(\frac{(3(k+1)) !}{(3 !)^{k+1}}=\frac{(3 k+3) !}{(3 !)^k(3 !)}\)= \(\frac{(3 k) !}{(3 !)^k} \cdot \frac{(3 k+3)(3 k+2)(3 k+1)}{6}\)

= \(l \cdot \frac{(k+1)(3 k+2)(3 k+1)}{2}\)

Now,

If k is even then,

k = 2r

⇒ 3k + 2 = 6r + 2

= 2(3r+1)

and hence 2 ∣ 3k + 2

If k is odd then,

k = 2r + 1

⇒ k + 1 = 2r + 2

= 2(r+1)

and hence 2∣k + 1

Therefore we conclude \(\frac{(k+1)(3 k+2)(3 k+1)}{2}\) is an integer, therefore \(\frac{(3(k+1)) !}{(3 !)^{k+1}}\) is an integer.

So by mathematical induction we have, (3n)!/(3!)^{n} is an integer for all n ≥ 0.

We have proved that the expression(3n)!/(3!)^{n} is an integer for all n ≥ 0.

**Page 25 Problem 18 Answer**

We are given a statement,

The product of any three consecutive integers is divisible by 6.

We have to prove the above statement.

Here a|b means a divides b

Let the three consecutive integers be

n, (n+1), (n+2).

Since 6 = 2.3 and gcd(2,3) = 1

If n is even, then,

2|n

⇒ 2|n(n+1)(n+2)

If n is odd, then n+1 is even and hence,

2|(n+1)

⇒ 2|n(n+1)(n+2)

Now, by division algorithm, n = 3k+r, 0 ≤ r < 3.

If n = 3k + 1, then,

n+2 = 3k+3

= 3(k+1)

and thus

3|(n+1)

⇒ 3|n(n+1)(n+2)

If n – 3k + 2, then

n+1 = 3k+3

= 3(k+1)

and thus

3|(n+1)

⇒ 3|n(n+1)(n+2)

Therefore we have

2|n(n+1)(n+2) and 3|n(n+1)(n+2), thus 6|n(n+1)(n+2)

We have proved that the product of any three consecutive integers is divisible by 6.

**Page 25 Problem 19 Answer**

We are given,

If a is an arbitrary integer, then 6 ∣ a(a^{2}+11).

We have to establish the given assertion.

By division algorithm, a = 6q + r, 0 ≤ r < 6

If r = 0,

⟹ a = 6q

⟹ 6∣a

So, 6∣a(a^{2}+11).

If r = 1,

⟹ a = 6q + 1

⟹ (a^{2}+11) = 36q^{2} + 12q + 12

= 6(6q^{2}+2q+2)

So, 6∣(a^{2}+11)

⟹ 6∣a(a^{2}+11)

If r = 2

⟹ a = 6q + 2

= 2(3q+1)

So,

2∣a and (a^{2}+11)

(a^{2}+11) = 36q^{2} + 24q + 15

= 3(12q^{2}+8q+5)

So, 3∣(a^{2}+11)⟹6∣a(a^{2}+11)

⟹ 6a(a^{2}+11)

If r = 3

⟹ a = 6q + 3

= 3(2q+1)

So, 3∣a

(a^{2}+11) = 36q^{2} + 36q + 20

(a^{2}+11) = 2(18q^{2}+18q+10)

So,

2∣(a^{2}+11) ⟹ 6∣a(a^{2}+11)

If r = 4

⟹ a = 6q + 4

= 2(3q+2)

So,

2∣a and (a^{2}+11)

(a^{2}+11) = 36q^{2} + 24q + 27

= 3(12q^{2}+8q+9)

So, 3∣(a^{2}+11) ⟹ 6∣a(a^{2}+11)

⟹ 6a(a^{2}+11)

If r = 5,

⇒ a = 6q + 5

⇒ (a^{2}+11) = 36q^{2} + 60q + 36

= 6(6q^{2}+10q+6)

So, 6∣(a^{2}+11)

⇒ 6 ∣ a(a^{2}+11)

Therefore in all cases 6 ∣ a(a^{2}+11)

We have proved that if a is an arbitrary integer, then 6∣a(a^{2}+11).

We are given,

If a is an order integer, then 24 ∣ a(a^{2}−1)

We have to establish the given assertion.

Since a is odd then a is in the form

a = 4k + 1 or

a = 4k + 3

= 4k−1.

Let a = 4k + 1

⟹ a^{2} = 16k^{2} + 8k + 1

= 8(2k^{2}+k) + 1

so, a^{2}= 8m + 1 where

m = 2k^{2} + k.

Thus,a(a^{2}−1) = (4k+1)(8m+1)

= 32km+8m

= 8(4km+m).

So 8∣a(a^{2}−1)⋯(1)

Similarly if a = 4k−1,k ∈ Z.

If r = 0

⇒ 3∣a

⇒ 3∣a(a^{2}−1).

If r = 1

⇒ a = 3q + 1

⇒ a^{2} − 1 = 9q^{2} + 6q

= 3(3q^{2}+2q).

So,3∣(a^{2}−1)

⟹ 3a(a^{2}−1)

If r = 2

⟹ a = 3q + 2

⟹ a^{2}−1 = 9q^{2} + 12q + 3

= 3(3q^{2}+4q+1).

So, 3∣(a^{2}−1)

⟹ 3a(a^{2}−1)

Since,

gcd(8,3) = 1

24 ∣ a(a^{2}−1)

We have proved that If a is an odd integer, then 24|a(a^{2}-1).

We are given that a and b are odd integers.

We have to prove that 8∣(a^{2}−b^{2})

Assuming that a,b are odd integers, then we have three cases,

If a = 4k+1

b = 4m+1

then,

a^{2}−b^{2} = (16k^{2}+8k+1)−(16m^{2}+8m+1)

= 16(k^{2}−m^{2})+8(k−m)

= 8(2(k^{2}−m^{2})+(k−m)).

Hence 8∣a^{2}−b^{2}

If a = 4k−1

b = 4m−1

then,

a^{2}−b^{2} = (16k^{2}−8k+1)−(16m^{2}−8m+1)

= 16(k^{2}−m^{2})−8(k−m)

= 8(2(k^{2}−m^{2})−(k−m))

Hence 8∣a^{2}−b^{2}

If a = 4k−1

b = 4m + 1

then,

a^{2} − b^{2} = (16k^{2}−8k+1) − (16m^{2}+8m+1)

= 16(k^{2}−m^{2}) + 8(k+m)

= 8(2(k^{2}−m^{2}) + (k+m)).

Hence 8∣a^{2}−b^{2}

Therefore we conclude that 8∣a^{2}−b^{2}

We have proved that if a and b are odd integers, then 8∣(a^{2}−b^{2})

We are given an assertion,

If a is an integer not divisible by 2 or 3, then 24∣(a^{2}+23).

We have to prove the assertion.

As a is not divisible by 2, then a is odd. Thus a=4k+1 or 4k−1

Since a is not divisible by 3,Thus a = 3q + 1 or 3q + 2

Therefore we have four cases.

**Case 1**

If a = 4k + 1

= 3q + 1

So,

(a^{2}+23) = (16k^{2}+8k+24)

(a^{2}+23) = 8(2k^{2}+k+3)

Thus 8∣(a^{2}+23)…(1)

Also,

(a^{2}+23) = 9q^{2} + 6q + 24

(a^{2}+23) = 3(3q^{3}+2q+8)

Thus 3∣(a^{2}+23)…(2)

Therefore from(1) and (2) we have, 24∣(a^{2}+23)

**Case 2**

If a = 4k−1

= 3q + 2

So,

(a^{2}+23) = (16k^{2}−8k+24)

= 8(2k^{2}−k+3).

Thus 8∣(a^{2}+23)…(1)

Also,

(a^{2}+23) = 9q^{2} + 12q + 27

(a^{2}+23) = 3(3q^{3}+4q+9)

Thus 3∣(a^{2}+23)…(2)

Therefore from(1) and (2) we have, 24∣(a^{2}+23)

**Case 3**

If a = 4k + 1

= 3q + 2

So,

(a^{2}+23) = (16k^{2}+8k+24)

(a^{2}+23) = 8(2k^{2}+k+3)

Thus 8∣(a^{2}+23)…(1)

Also,

(a^{2}+23) = 9q^{2} + 12q + 27

(a^{2}+23) = 3(3q^{3}+4q+9)

Thus 3∣(a^{2}+23)…(2)

Therefore from(1) and (2) we have,

24∣(a^{2}+23)

**Case 4**

If a = 4k − 1

= 3q + 1

So,

(a^{2}+23) = (16k^{2}−8k+24)

= 8(2k^{2}−k+3).

Thus 8∣(a^{2}+23)…(1)

Also,

(a^{2}+23) = 9q^{2} + 6q + 24

(a^{2}+23) = 3(3q^{2}+2q+8)

Thus 3∣(a^{2}+23)…(2)

Therefore from(1) and (2) we have,

24∣(a^{2}+23)

Therefore we conclude that 24∣(a^{2}+23)

Hence we have proved that if a is an integer not divisible by 2 or 3, then 24∣(a^{2}+23).

We have to prove that if a is an arbitrary integer, then 360∣a^{2}(a^{2}−1)(a^{2}−4).

We have,

a^{2}(a^{2}−1)(a^{2}−4) = a^{2}(a+1)(a−1)(a+2)(a−2)

= (a−2)(a−1)(a)(a+1)(a+2)(a)

Also 360 = 5 × 9 × 8 where5,8,9 are relatively prime.

Now we know that(a−2)(a−1)(a)(a+1)(a+2) is divisble by 24 and 120, and therefore it′s divisble by 8 and 5

Also,(a−2)(a−1)(a) and (a+1)(a+2)(a) are both divisible by 6 and so are both divisible by 3.

Thus(a−2)(a−1)(a)(a+1)(a+2)(a) is divisible by 9.

Therefore,

5⋅8⋅9∣a^{2}(a^{2}−1)(a^{2}−4)

⇒ 360∣a^{2}(a^{2}−1)(a^{2}−4)

We have proved that if a is an arbitrary integer, then 360∣a^{2}(a^{2}−1)(a^{2}−4).

**Page 25 Problem 20 Answer**

We are given,

gcd(a,b) = 1

gcd(a,c) = 1

We have to prove that gcd(a,bc) = 1

We have,

gcd(a,b) = 1

gcd(a,c) = 1

Therefore,

1 = ax + by

1 = af + ct

for some x,y,f,t in Z

Hence we have,

1 = (ax+by)(af+ct)

= a^{2}xf + abyf + acxt + bcyt

= a(axf+byf+cxt) + bcyt

= ak_{1}+ bck_{2}

Therefore a, bc are relatively prime.

Hence, gcd(a,bc) = 1

We have proved that if,

gcd(a,b) = 1,

and gcd(a,c) = 1,

then gcd(a,bc) = 1

We are given,

gcd(a,b) = 1

c∣a

We have to prove gcd(b,c) = 1

We have gcd(a,b) = 1

Therefore ax + by = 1 for some x,y in Z

Also as c∣a

There exist as in Z such that cs=a, where cs belongs to Z

Therefore,

cst + bf = 1

Thus gcd(b,c) = 1

We have proved that if gcd(a,b) = 1 and c∣a then, gcd(b,c) = 1

We have to prove that if gcd(a,b) = 1 then,

gcd(ac,b) = gcd(c,b)

Let gcd(c,b) = d, then there exists x,y in Z such that,

d = cx + by.

Since d∣c there existsn such that dn = c, and so we have,

d(na) = ca⟹d∣ca

⇒ d∣ca.

Now let k∣ac and k∣b, then there exists m such that km = b, therefore

d = cx + kmy.

Since gcd(a,b) = 1, there exists p,q such that,

ap + bq = 1

Therefore,

apc + bqc = c

⇒ d = (apc+bqc)x + kmy

d = acpx + knqcx + kmy

Butk∣ac

Hence there existsr such that kr = ac

Therefore,

d = krpx + knqcx + kny

d = k(rpx+nqcx+ny)

And hence k∣d and therefore gcd(c,b) = gcd(ac,b)

We have proved that if gcd(a,b) = 1 then,

gcd(ac,b) = gcd(c,b)

We are given,

gcd(a,b) = 1

c∣a+b

We have to prove that,

gcd(a,c) = 1

gcd(b,c) = 1

If gcd(a,b) = c then there exists, x,y in Z such that,

c = ax + by

We have,c∣a + b therefore, there existsn such that cn = a + b and hence,

a = cn−b

Therefore,

(cn−b)x + by = 1

cnx − bx + by = 1

cnx + b(y−x) = 1

So gcd(c,b) = 1

Similarly,

cn − a = b

ax + (cn−a)y = 1

ax + cny − ay = 1

a(x−y) + cny = 1

So,gcd(c,a) = 1.

We have proved that if gcd(a,b) = 1, and c∣a + b then,

gcd(a,c) = 1

gcd(b,c) = 1

We are given,

gcd(a,b) = 1

d∣ac

d∣bc

We have to prove that d∣c

We have,

gcd(a,b) = 1, then for some x,y in Z

ax + by = 1

Therefore,

c = cax + cby…(1)

Now as d∣ac

Therefore,

ac = dr

c = \(\frac{d r}{a}\)

Also,

d∣bc

⇒ bc = dm

⇒ c = \(\frac{d m}{b}\)

Using above (1) we get,

c = \(\frac{d r}{a} a x+\frac{d m}{b} b y\)

c = drx + dmy

c = d(rx+my)

Therefore d|c

We have proved if gcd(a,b) = 1,d∣ac, and d∣bc, then d∣c.

**Page 26 Problem 21 Answer**

Given : d ∣ n is given. We need to prove 2^{d}−1∣2^{n}−1.

We will do it by using the identity.

It is given that d∣n.

We can also write it as dm = n, here m is some integer.

So we can also write :

2^{n}−1 = 2^{dm}−1

= (2^{d})^{m}−1

Now we will use the identity :

x^{k-1} = (x−1)(x^{k-1}+x^{k-2}+⋯+x+1)

Now we have ,

2^{n}−1 = (2^{d})^{m}−1

= (2^{d}-1)((2^{d})^{m-1}+(2^{d})^{m-2}+⋯+(2^{d})+1)

Hence, 2^{d}−1∣2^{n}−1.

2^{d} – 1|2^{n}-1 by using the identity:

x^{k-1} = (x-1)(x^{k-1} + x^{k-2}+…+x+1).

2^{35} – 1 is given.

We will verity that 2^{35}-1 is divisible by 31 and 127.

We will do it by using the identity.

We have :

31 = 2^{5}−1 and 127=2^{7}−1

And we have that 5∣35.

Now using the identity :

x^{k-1} = (x−1)(x^{k-1}+x^{k-2}+⋯+x+1) we have ,

31 = 2^{5}−1∣2^{35}−1

And similarly we have 7∣35.

So, again using the identity we get :

127 = 2^{7}−1∣2^{35}−1

Yes, 2^{35}−1 is divided by 31 and 127.

**Page 26 Problem 22 Answer**

Given : Let t_{n}denote the nth triangular number.

We will find for what values of n does t_{n} divide the sum t_{1}+t_{2}+⋯+t_{n}.

We will do it by using the formula above.

We have:

t_{1} + t_{2} + …+ t_{n} = \(\frac{n(n+1)(n+2)}{6}\)

t_{n} = \(\frac{n(n+1)}{2}\).

Now, therefore:

\(\frac{t_1+t_2+\cdots+t_n}{t_n}=\frac{\frac{n(n+1)(n+2)}{6}}{\frac{n(n+1)}{2}}\)= \(\frac{n+2}{3}\)

So, at the \(\frac{n+2}{3}\) integer tn divides t_{1} + t_{2} + …. + t_{n}.

Therefore, the form of n is n = 3k + 1 and the values of n are 1,4,7,10,……

At the \(\frac{n+2}{3}\) integer tn divides t_{1} + t_{2} + …. + t_{n.}

Therefore, the form of n is n = 3k + 1 and the values of n are 1,4,7,10,….

**Page 26 Problem 23 Answer**

a | b is given.

We need to show that a| gcd(a,b)gcd(a,c).

We will prove it by using the formula of gcd(a,b).

a|bc is given that means bc = ax where x∈Z (let us consider this equation one).

Now we have :

gcd(a,b) = am + bn ,where m,n∈Z and

gcd(a,c) = ar + bs , where r,s∈Z.

Now we have :

gcd(a,b)⋅gcd(a,c) = a^{2}mr + acms + abrn + bcns

Now using equation one we get :

= a^{2}mr + acms + abrn + axns

= a(amr+cms+brn+xns)

Hence , a ∣ gcd(a,b)⋅gcd(a,c) is proved.

Yes, a∣gcd(a,b)⋅gcd(a,c) is proved.