Skip to main content

# 2.4: Arithmetic of divisibility

This page is a draft and is under active development.

$$\newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} }$$ $$\newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}}$$$$\newcommand{\id}{\mathrm{id}}$$ $$\newcommand{\Span}{\mathrm{span}}$$ $$\newcommand{\kernel}{\mathrm{null}\,}$$ $$\newcommand{\range}{\mathrm{range}\,}$$ $$\newcommand{\RealPart}{\mathrm{Re}}$$ $$\newcommand{\ImaginaryPart}{\mathrm{Im}}$$ $$\newcommand{\Argument}{\mathrm{Arg}}$$ $$\newcommand{\norm}[1]{\| #1 \|}$$ $$\newcommand{\inner}[2]{\langle #1, #2 \rangle}$$ $$\newcommand{\Span}{\mathrm{span}}$$ $$\newcommand{\id}{\mathrm{id}}$$ $$\newcommand{\Span}{\mathrm{span}}$$ $$\newcommand{\kernel}{\mathrm{null}\,}$$ $$\newcommand{\range}{\mathrm{range}\,}$$ $$\newcommand{\RealPart}{\mathrm{Re}}$$ $$\newcommand{\ImaginaryPart}{\mathrm{Im}}$$ $$\newcommand{\Argument}{\mathrm{Arg}}$$ $$\newcommand{\norm}[1]{\| #1 \|}$$ $$\newcommand{\inner}[2]{\langle #1, #2 \rangle}$$ $$\newcommand{\Span}{\mathrm{span}}$$$$\newcommand{\AA}{\unicode[.8,0]{x212B}}$$

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 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 $$\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).□$$

##### 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$$.

This page titled 2.4: Arithmetic of divisibility is shared under a CC BY-NC-SA license and was authored, remixed, and/or curated by Pamini Thangarajah.

• Was this article helpful?