2.4: Arithmetic of divisibility

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 \in \mathbb{Z}\) such that \(a+b=c\). If \(d \in \mathbb{Z_+}\) divides any two of \(a,b\) and \(c\), then \(d\) divides the third one.

Proof:

Proof:(by cases)

Case 1: Suppose \(d \mid a \) and \(d \mid b\). We shall show that \(d \mid c\).

Since \(d \mid a \) and \(d \mid b\), \( a=dm \) and \( b=dk \), for some \(m, k \in \mathbb{Z}\).

Consider, \( c=a+b=dm+dk=d(m+k).\)

Since \((m + k )\in \mathbb{Z} \), \( d \mid c \) .

Case 2: Suppose \(d \mid a \) and \(d \mid c\). We shall show that \(d \mid b\).

Since \(d \mid a \) and \(d \mid c\), \(a = dm\) and \(c = dk\), for some \(m, k \in \mathbb{Z}\).

Consider, \( b=c-a=d(k-m).\)

Since \((k - m)\in \mathbb{Z}\),\(d \mid b \) .

Case 3: Suppose \(d \mid b \) and \(d \mid c\). We shall show that \(d \mid a\).

Since \(d \mid b\) and \(d \mid c\), \(b = dm \) and \(c = dk\), with \(m, k \in \mathbb{Z}\).

Consider,\( a=c-b=d(k-m).\)

Since \((k - m)\in \mathbb{Z}\), \(d \mid a \).

Having examined all possible cases, given a + b = c, then if \(d \in \mathbb{Z_+}\) divides any two of \(a,b\) and \(c\), then \(d\) divides the third one. \( \Box\)

Theorem: Divisibility theorem II (MULTIPLE)

Let \(a,b,c \in \mathbb{Z}\) such that \(a \mid b\). Then \(a \mid bc\).

Proof:

Let \(a,b,c \in \mathbb{Z}\) such that \(a \mid b\).

We shall show that \(a \mid bc\).

Consider that since a | b, b = ak, \(k \in \mathbb{Z}\).

Further consider bc = a(ck).

Since \(ck \in \mathbb{Z}\), a | bc.\( \Box\)

Theorem: Arithmetic of Divisibility

Let \(a,b,c,d \in \mathbb{Z}\). Then

1. if \(a \mid b \) and \(a \mid c\) then \(a \mid (b+c)\).
2. if \(a \mid b \) and \(a \mid c\) then \(a \mid (bc)\).
3. if \(a \mid b \) and \(c \mid d\) then \((ac) \mid (bd)\).

Proof:

Proof of 1:

Let \(a,b,c,d \in \mathbb{Z}\).

We shall show that if \(a \mid b \) and \(a \mid c\) then \(a \mid (b + c)\).

Since \( a|b, b=ak, k \in \mathbb{Z}\) and since \(a | c, c = am, \, m \in \mathbb{Z}\).

Consider, \( b + c = a(k + m)\).

Since \(k + m \in \mathbb{Z}\), \(a | (b + c)\).\( \Box\)

Proof of 2:

Let \(a,b,c,d \in \mathbb{Z}\).

We shall show that if \(a \mid b \) and \(a \mid c\) then \(a \mid (bc)\).

Since \( a|b, b=ak, k \in \mathbb{Z}\) and since \(a | c, c = am, \, m \in \mathbb{Z}\).

Consider \( bc = a(akm).\)

Since \(akm \in \mathbb{Z}\), \(a | (bc)\).\( \Box\)

Proof of 3:

Let \(a,b,c,d \in \mathbb{Z}\).

We shall show that if \(a \mid b \) and \(c \mid d\) then \( (ac) \mid (bd)\).

Since\( a|b, b=ak, k \in \mathbb{Z}\) and since \(a | c, c = am, \, m \in \mathbb{Z}\).

Consider \( bd = (ak)(cm) = ac(km).\)

Since \(km \in \mathbb{Z}\),\( (ac) | (bd)\).\( \Box\)

Example \(\PageIndex{1}\):

Let \(a,b,c,d \in \mathbb{Z}\) such that \(a \mid b \) and \(c \mid d\). Is it always true that \((a+c) \mid (b+d)\) ?

In other words, if a teacher could share 6 apples among 6 boys and 8 oranges among 4 girls equally, is it possible for the teacher to share the 14 fruits equally among the 10 children?

Example \(\PageIndex{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 \in \mathbb{Z}.\)

Further consider \(b-9 =7(k), k \in \mathbb{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 \in \mathbb{Z}.\)

Thus, \(7 | (a + b).\square\)

Example \(\PageIndex{3}\):

Let \(a\) and \(b\) be positive integers. Prove or disprove the following statements:

1. If \( a|b\) then \(a^2|b^3\).

2. If \( a^2|b^3\) 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 \in \mathbb{Z_+}\).

Consider \(b^3=(am)^3=a^3m^3=a^2(am^3).\)

Since \(am^3 \in \mathbb{Z_+}, a^2|b^3.\) 

2. This statement is false. Counterexample:

Choose \(a=3^3, b=3^2\). Then  \(a^2=3^6=b^3.\)

Hence \( a^2|b^3\) but  \(a\not \mid b\).