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 a2∣ bc
Let a∣b and a∣c then, ∃ x,y ∋ ax = b,ay = c
∴ (ax)(ay) = bc = a2xy ⟹ a2 ∣ bc
Thus, we verified that if a∣b and a∣c, then a2 ∣ 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 = a2xy ⟹ 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 52(k+1) + 7 = 52(52k+7) + (7−52⋅7).
For n = 1:52n + 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 ∣ 52k + 7 ∴ ∃ x ∋ 8x = 52k + 7
Now, for n = k + 1
52(k+1) + 7 = 52⋅52k + 7
= 52(52k+7) − 52⋅7 + 7
= 52(8x) − 52 − 7(52−1)
= 52(8x) − 7(24)
= 8x(25) − 8(7⋅3)
= 8(25x−21)
∴ 8 ∣ 5k+1
Thus, by mathematical induction for n ≥ 1,8 ∣ 5n
Thus, we have to use mathematical induction to establish the divisibility statements 8 ∣ 52n + 7
Here, we have to use mathematical induction to establish the divisibility statements, 15 ∣ 24n − 1
For, n = 1 : 24 − 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 ∣ (24k−1) ∴ ∃ x ∋ 15x = 24k − 1
Now, for n = k + 1
24(k+1) − 1 = 24⋅24k − 1 + 24 − 24
= 24(24k−1) + (24−1)
= 24(15x) + 15
= 15(x24+1)
∴ 15 ∣ 24(k+1) − 1
Thus, by mathematical induction for n ≥ 1,15 ∣ 24n − 1
Thus, we use mathematical induction to establish the divisibility statements, 15 ∣ 24n − 1
Here, we have to use mathematical induction to establish the divisibility statements, 5 ∣ 33n+1 + 2n+1
For n = 1 : 33+1 + 22 = 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 ∣(33k+1 + 2k+1) ∴ ∃ x ∋ 5x = 33k+1 + 2k+1
Now for n = k + 1
33(k+1)+1 − 2k+2 = 33k+4 − 2k+2
= 33⋅33k+1 + 2⋅2k+1 + 3⋅2k+1 − 33⋅2k+1
= 33(33k+1 + 2k+1) − 2k+1(33−2)
= 33(5x) − 2k+1(25)
= 5(x33 − 5⋅2k+1)
∴ 5 ∣ (33n+1 + 2n+1)
Thus, by mathematical induction for n ≥ 1, 5 ∣ 24n − 1
Thus, we use mathematical induction to establish the divisibility statements, 5 ∣ 24n−1
Here, we have to use mathematical induction to establish the divisibility statements, 21 ∣ 4n+1 + 52n-1
For ,n = 1: 42 + 51 = 21 and 21 ∣ 21.Suppose, it’s true for n = k then we want to prove it for n = k + 1.
Let 21 ∣ (4k+1+52k-1) ∴ ∃ x ∋ 21x = 4k+1 + 52k-1
Now, for n = k + 1
43(k+2) − 52(k+1)−1 = 4k+2 − 52k+1
= 4⋅4k+1 + 52⋅52k-1 + 4⋅52k-1− 4⋅52k-1
= 4(4k+1 + 52k-1) + 21(52k-1)
= 4(21x) + 21(52k-1)
= 21(4x+52k-1)
∴ 21 ∣ (4(k+1)+1 + 52(k+1)-1)
Thus, by mathematical induction for n ≥ 1, 21∣(4k+1 + 52k+1)
Thus, we use mathematical induction to establish the divisibility statements, 21 ∣ 4n+1 + 52n-1
Here, we have to use mathematical induction to establish the divisibility statements, 24 ∣ 2⋅7n + 3⋅5n−5
Now we want to prove by mathematical induction that 24 ∣ 4⋅7k + 20 for s = 1: 4⋅71 + 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⋅7s + 20 ∴ ∃ x ∋ 24x = 4⋅7s + 20
Now, for n = k + 1
4⋅7s+1 + 20 = 7(4⋅7s)+20
= 7(4⋅7s+20) + 20 − 140
= 7(24y) − 24⋅5
∴ ∃ q ∋ 24q = 4⋅7k + 20
∴ eq (1) = 5(24x) + 24q
Thus, by mathematical induction for n ≥ 1,24 ∣ 2⋅7n + 3⋅5n−5
Thus, we use mathematical induction to establish the divisibility statements, 24 ∣ 2⋅7n + 3⋅5n−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(2a2+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(2a2+7)
Case 2: If a = 3q + 1 then, a2 = 9q2 + 6q + 1,
⟹ 2a2 + 7 = 2(9q2+6q+1) + 7
= 18q2 + 12q + 9 = 3(6q2+4q+3)
thus 3∣∣2a2 + 7 ⟹ 3∣∣a(2a2+7)
Case 3: If a = 3q + 2 then, a2 = 9q2 + 12q + 4,
⟹ 2a2 + 7 = 2(9q2+12q+4) + 7
= 18q2 + 24q + 15 = 3(6q2+8q+5)
Thus 3 ∣ 2a2 + 7 ⟹ 3 ∣ a(2a2+7)
Thus, we verified 3 ∣ a(2a2+7)
Here, we have to verify that if a is odd ,then 32 ∣ (a2+3)(a2+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 a2 = 16q2 + 8q + 1
⟹ a2 + 3 = 16q2 + 8q + 4 = 4(4q2+2q+1)⋯(1)
a2 + 7 = 16q2 + 8q + 8 = 8(2q2+q+1)⋯(2)
From (1) and (2)
(a2+3)(a2+7) = [4(4q2+2q+1)][8(2q2+q+1)]
= 32(4q2+2q+1)(2q2+q+1)
Thus 32 ∣ (a2+3)(a2+7)
Case 2 : If a a = 4q + 3 then,
a2 = 16q2 + 24q + 9
⟹ a2 + 3 = 16q2 + 24q + 12 = 4(4q2+6q+3)⋯(1)
a2 + 7 = 16q2 + 24q + 16 = 8(2q2+3q+2)⋯(2)
from (1) and (2)
(a2+3)(a2+7) = [4(4q2+6q+3)][8(2q2+3q+2)]
= 32(4q2+6q+3)(2q2+3q+2)
Thus 32 ∣ (a2+3)(a2+7)
Thus, we verified if a is odd ,then 32∣(a2+3)(a2+7)
Page 25 Problem 7 Answer
Here, we have to prove that if a and b are both odd integers, then 16 ∣ a4 + b4 − 2
Since a and b are both odd integers then a = 2r + 1 and b = 2s + 1 where k, l ∈ Z.
Now,
a4 + b4 – 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(r4+s4) + 32(r3+s3) + 24r2 + 8r + 24s2 + 8s
to prove that 16 ∣ a4 + b4 − 2 we just need 16 ∣ 24r2 + 8r
If r is odd then r = 2k + 1,then
24(2k+1)2 + 8(2k+1)
= 96k2 + 96k + 24 + 16k + 8
= 96k2 + 96k + 16k + 32
= 16(8k2+8k+k+2)
If r is even then r = 2k,thus
24(2k)2 + 8(2k) = 96k2 + 16k = 16(8k2+k)
Thus, 16 ∣ 24r2 + 8r, similarly 16 ∣ 24s2 + 8s
∴ 16 ∣ a4 + b4 − 2
Thus, we prove that if a and b are both odd integers, then 16 ∣ a4 + b4 − 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,
a2 + b2 = (2r+1)2 + (2s+1)2 = 4r2 + 4r + 1 + 4s2 + 4s + 1 = 4(r2+s2+r+s) + 2 = 4k + 2
where, k = r2 + s2 + r + s
Suppose a2 + b2 is a perfect square, then a2 + b2 = c2 = 4k + 2 = 2(2k+1)
Then c2 is even ⇒ c is even, so c = 2m ⟹ c2 = 4m2 = 4l where l = m2
Thus, a2 + b2 = c2 ⟹ 4k + 2 = 4l,this contradict the uniqueness of division algorithm, ∴ a2 + b2 ≠ c2 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) = (k2+3k)(k2+3k+2)
=((k2+3k+1)−1)((k2+3k+1)+1)
= (k2+3k+1)2 − 12
Now let(k2+3k+1) = p where p is some integer.
Hence (k2+3k+1)2 = p2
Therefore we have,
k(k+3)(k+1)(k+2) = p2 − 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 − a3
Solving (a+1)3 − a3 we get,
(a+1)3 − a3 = a3 + 3a2 + 3a + 1 − a3
= 3a2 + 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 − a3.
Hence we have proved that 2 ∤ (a+1)3 − a3.
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(a2+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(a2+11).
If r = 1,
⟹ a = 6q + 1
⟹ (a2+11) = 36q2 + 12q + 12
= 6(6q2+2q+2)
So, 6∣(a2+11)
⟹ 6∣a(a2+11)
If r = 2
⟹ a = 6q + 2
= 2(3q+1)
So,
2∣a and (a2+11)
(a2+11) = 36q2 + 24q + 15
= 3(12q2+8q+5)
So, 3∣(a2+11)⟹6∣a(a2+11)
⟹ 6a(a2+11)
If r = 3
⟹ a = 6q + 3
= 3(2q+1)
So, 3∣a
(a2+11) = 36q2 + 36q + 20
(a2+11) = 2(18q2+18q+10)
So,
2∣(a2+11) ⟹ 6∣a(a2+11)
If r = 4
⟹ a = 6q + 4
= 2(3q+2)
So,
2∣a and (a2+11)
(a2+11) = 36q2 + 24q + 27
= 3(12q2+8q+9)
So, 3∣(a2+11) ⟹ 6∣a(a2+11)
⟹ 6a(a2+11)
If r = 5,
⇒ a = 6q + 5
⇒ (a2+11) = 36q2 + 60q + 36
= 6(6q2+10q+6)
So, 6∣(a2+11)
⇒ 6 ∣ a(a2+11)
Therefore in all cases 6 ∣ a(a2+11)
We have proved that if a is an arbitrary integer, then 6∣a(a2+11).
We are given,
If a is an order integer, then 24 ∣ a(a2−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
⟹ a2 = 16k2 + 8k + 1
= 8(2k2+k) + 1
so, a2= 8m + 1 where
m = 2k2 + k.
Thus,a(a2−1) = (4k+1)(8m+1)
= 32km+8m
= 8(4km+m).
So 8∣a(a2−1)⋯(1)
Similarly if a = 4k−1,k ∈ Z.
If r = 0
⇒ 3∣a
⇒ 3∣a(a2−1).
If r = 1
⇒ a = 3q + 1
⇒ a2 − 1 = 9q2 + 6q
= 3(3q2+2q).
So,3∣(a2−1)
⟹ 3a(a2−1)
If r = 2
⟹ a = 3q + 2
⟹ a2−1 = 9q2 + 12q + 3
= 3(3q2+4q+1).
So, 3∣(a2−1)
⟹ 3a(a2−1)
Since,
gcd(8,3) = 1
24 ∣ a(a2−1)
We have proved that If a is an odd integer, then 24|a(a2-1).
We are given that a and b are odd integers.
We have to prove that 8∣(a2−b2)
Assuming that a,b are odd integers, then we have three cases,
If a = 4k+1
b = 4m+1
then,
a2−b2 = (16k2+8k+1)−(16m2+8m+1)
= 16(k2−m2)+8(k−m)
= 8(2(k2−m2)+(k−m)).
Hence 8∣a2−b2
If a = 4k−1
b = 4m−1
then,
a2−b2 = (16k2−8k+1)−(16m2−8m+1)
= 16(k2−m2)−8(k−m)
= 8(2(k2−m2)−(k−m))
Hence 8∣a2−b2
If a = 4k−1
b = 4m + 1
then,
a2 − b2 = (16k2−8k+1) − (16m2+8m+1)
= 16(k2−m2) + 8(k+m)
= 8(2(k2−m2) + (k+m)).
Hence 8∣a2−b2
Therefore we conclude that 8∣a2−b2
We have proved that if a and b are odd integers, then 8∣(a2−b2)
We are given an assertion,
If a is an integer not divisible by 2 or 3, then 24∣(a2+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,
(a2+23) = (16k2+8k+24)
(a2+23) = 8(2k2+k+3)
Thus 8∣(a2+23)…(1)
Also,
(a2+23) = 9q2 + 6q + 24
(a2+23) = 3(3q3+2q+8)
Thus 3∣(a2+23)…(2)
Therefore from(1) and (2) we have, 24∣(a2+23)
Case 2
If a = 4k−1
= 3q + 2
So,
(a2+23) = (16k2−8k+24)
= 8(2k2−k+3).
Thus 8∣(a2+23)…(1)
Also,
(a2+23) = 9q2 + 12q + 27
(a2+23) = 3(3q3+4q+9)
Thus 3∣(a2+23)…(2)
Therefore from(1) and (2) we have, 24∣(a2+23)
Case 3
If a = 4k + 1
= 3q + 2
So,
(a2+23) = (16k2+8k+24)
(a2+23) = 8(2k2+k+3)
Thus 8∣(a2+23)…(1)
Also,
(a2+23) = 9q2 + 12q + 27
(a2+23) = 3(3q3+4q+9)
Thus 3∣(a2+23)…(2)
Therefore from(1) and (2) we have,
24∣(a2+23)
Case 4
If a = 4k − 1
= 3q + 1
So,
(a2+23) = (16k2−8k+24)
= 8(2k2−k+3).
Thus 8∣(a2+23)…(1)
Also,
(a2+23) = 9q2 + 6q + 24
(a2+23) = 3(3q2+2q+8)
Thus 3∣(a2+23)…(2)
Therefore from(1) and (2) we have,
24∣(a2+23)
Therefore we conclude that 24∣(a2+23)
Hence we have proved that if a is an integer not divisible by 2 or 3, then 24∣(a2+23).
We have to prove that if a is an arbitrary integer, then 360∣a2(a2−1)(a2−4).
We have,
a2(a2−1)(a2−4) = a2(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∣a2(a2−1)(a2−4)
⇒ 360∣a2(a2−1)(a2−4)
We have proved that if a is an arbitrary integer, then 360∣a2(a2−1)(a2−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)
= a2xf + abyf + acxt + bcyt
= a(axf+byf+cxt) + bcyt
= ak1+ bck2
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 2d−1∣2n−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 :
2n−1 = 2dm−1
= (2d)m−1
Now we will use the identity :
xk-1 = (x−1)(xk-1+xk-2+⋯+x+1)
Now we have ,
2n−1 = (2d)m−1
= (2d-1)((2d)m-1+(2d)m-2+⋯+(2d)+1)
Hence, 2d−1∣2n−1.
2d – 1|2n-1 by using the identity:
xk-1 = (x-1)(xk-1 + xk-2+…+x+1).
235 – 1 is given.
We will verity that 235-1 is divisible by 31 and 127.
We will do it by using the identity.
We have :
31 = 25−1 and 127=27−1
And we have that 5∣35.
Now using the identity :
xk-1 = (x−1)(xk-1+xk-2+⋯+x+1) we have ,
31 = 25−1∣235−1
And similarly we have 7∣35.
So, again using the identity we get :
127 = 27−1∣235−1
Yes, 235−1 is divided by 31 and 127.
Page 26 Problem 22 Answer
Given : Let tndenote the nth triangular number.
We will find for what values of n does tn divide the sum t1+t2+⋯+tn.
We will do it by using the formula above.
We have:
t1 + t2 + …+ tn = \(\frac{n(n+1)(n+2)}{6}\)
tn = \(\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 t1 + t2 + …. + tn.
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 t1 + t2 + …. + tn.
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) = a2mr + acms + abrn + bcns
Now using equation one we get :
= a2mr + 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.