2.4: Arithmetic of divisibility
( \newcommand{\kernel}{\mathrm{null}\,}\)
Thinking out loud
If a teacher was able to share 6 apples among 6 boys and 8 oranges among 4 girls equally, is it possible for the teacher to share the 14 fruits with the 10 children equally?
Theorem: Divisibility theorem I (BASIC)
Let a,b,c∈Z such that a+b=c. If d∈Z+ divides any two of a,b and c, then d divides the third one.
- Proof:
-
Proof:(by cases)
Case 1: Suppose d∣a and d∣b. We shall show that d∣c.
Since d∣a and d∣b, a=dm and b=dk, for some m,k∈Z.
Consider, c=a+b=dm+dk=d(m+k).
Since (m+k)∈Z, d∣c .
Case 2: Suppose d∣a and d∣c. We shall show that d∣b.
Since d∣a and d∣c, a=dm and c=dk, for some m,k∈Z.
Consider, b=c−a=d(k−m).
Since (k−m)∈Z,d∣b .
Case 3: Suppose d∣b and d∣c. We shall show that d∣a.
Since d∣b and d∣c, b=dm and c=dk, with m,k∈Z.
Consider,a=c−b=d(k−m).
Since (k−m)∈Z, d∣a.
Having examined all possible cases, given a + b = c, then if d∈Z+ divides any two of a,b and c, then d divides the third one. ◻
Theorem: Divisibility theorem II (MULTIPLE)
Let a,b,c∈Z such that a∣b. Then a∣bc.
- Proof:
-
Let a,b,c∈Z such that a∣b.
We shall show that a∣bc.
Consider that since a | b, b = ak, k∈Z.
Further consider bc = a(ck).
Since ck∈Z, a | bc.◻
Theorem: Arithmetic of Divisibility
Let a,b,c,d∈Z. Then
- if a∣b and a∣c then a∣(b+c).
- if a∣b and a∣c then a∣(bc).
- if a∣b and c∣d then (ac)∣(bd).
- Proof:
-
Proof of 1:
Let a,b,c,d∈Z.
We shall show that if a∣b and a∣c then a∣(b+c).
Since a|b,b=ak,k∈Z and since a|c,c=am,m∈Z.
Consider, b+c=a(k+m).
Since k+m∈Z, a|(b+c).◻
Proof of 2:
Let a,b,c,d∈Z.
We shall show that if a∣b and a∣c then a∣(bc).
Since a|b,b=ak,k∈Z and since a|c,c=am,m∈Z.
Consider bc=a(akm).
Since akm∈Z, a|(bc).◻
Proof of 3:
Let a,b,c,d∈Z.
We shall show that if a∣b and c∣d then (ac)∣(bd).
Sincea|b,b=ak,k∈Z and since a|c,c=am,m∈Z.
Consider bd=(ak)(cm)=ac(km).
Since km∈Z,(ac)|(bd).◻
Example 2.4.1:
Let a,b,c,d∈Z such that a∣b and c∣d. Is it always true that (a+c)∣(b+d) ?
In other words, if a teacher was able to share 6 apples among 6 boys and 8 oranges among 4 girls equally, is it possible for the teacher to share the 14 fruits with the 10 children equally?
Example 2.4.2:
Let a and b be positive integers such that 7|(a+2b+5) and 7|(b−9). Prove that 7|(a+b).
Solution
Let a,b∈ℤ+s.t.7∣(a+2b+5) and 7∣(b−9).
Consider a+2b+5=7(m),m∈Z.
Further consider b−9=7(k),k∈Z.
Next consider a+2b+5−(b−9)=7m−7k.
a+b+14=7(m−k).
a+b=7(m−k−2),m−k−2∈Z.
Thus, 7|(a+b).□
Example 2.4.3:
Let a and b be positive integers. Prove or disprove the following statements:
1. If a|b then a2|b3.
2. If a2|b3 then a|b.
Solution
1. This statement is true.
Proof:
Let a and b be positive integers such that a|b. Then b=am,m∈Z+.
Consider b3=(am)3=a3m3=a2(am3).
Since am3∈Z+,a2|b3.
2. This statement is false. Counterexample:
Choose a=33,b=32. Then a2=36=b3.
Hence a2|b3 but a∤b.