$$\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}}$$

# 2.4 Arithmetic of divisibility

• Page ID
7428
•

$$\newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} }$$

$$\newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}}$$

Theorem: Divisibility theorem I

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:(by cases)

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

Consider that a = dm and b = dk, with $$m, k \in \mathbb{Z}$$.

Further, consider that c = a + b

= d(m + k).

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

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

Consider that a = dm and c = dk, with $$m, k \in \mathbb{Z}$$.

Further, consider that b = c - a

= d(k - m).

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

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

Consider that b = dm and c = dk, with $$m, k \in \mathbb{Z}$$.

Further, consider that a = c - b

= d(k - m).

Since $$(k - m)\in \mathbb{Z}$$, d | 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

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:

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

Consider that since a | b, b = ak, $$k \in \mathbb{Z}$$ and since a | c, c = am, $$m \in \mathbb{Z}$$.

Further, consider that 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)$$.

Consider that since a | b, b = ak, $$k \in \mathbb{Z}$$ and since a | c, c = am, $$m \in \mathbb{Z}$$.

Further, consider that 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)$$.

Consider that since a | b, b = ak, $$k \in \mathbb{Z}$$ and since c | d, d = cm, $$m \in \mathbb{Z}$$.

Further, consider that 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?