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}}} \)
\( \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}}\)
\( \newcommand{\vectorA}[1]{\vec{#1}} % arrow\)
\( \newcommand{\vectorAt}[1]{\vec{\text{#1}}} % arrow\)
\( \newcommand{\vectorB}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \)
\( \newcommand{\vectorC}[1]{\textbf{#1}} \)
\( \newcommand{\vectorD}[1]{\overrightarrow{#1}} \)
\( \newcommand{\vectorDt}[1]{\overrightarrow{\text{#1}}} \)
\( \newcommand{\vectE}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash{\mathbf {#1}}}} \)
\( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \)
\( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)
\(\newcommand{\avec}{\mathbf a}\) \(\newcommand{\bvec}{\mathbf b}\) \(\newcommand{\cvec}{\mathbf c}\) \(\newcommand{\dvec}{\mathbf d}\) \(\newcommand{\dtil}{\widetilde{\mathbf d}}\) \(\newcommand{\evec}{\mathbf e}\) \(\newcommand{\fvec}{\mathbf f}\) \(\newcommand{\nvec}{\mathbf n}\) \(\newcommand{\pvec}{\mathbf p}\) \(\newcommand{\qvec}{\mathbf q}\) \(\newcommand{\svec}{\mathbf s}\) \(\newcommand{\tvec}{\mathbf t}\) \(\newcommand{\uvec}{\mathbf u}\) \(\newcommand{\vvec}{\mathbf v}\) \(\newcommand{\wvec}{\mathbf w}\) \(\newcommand{\xvec}{\mathbf x}\) \(\newcommand{\yvec}{\mathbf y}\) \(\newcommand{\zvec}{\mathbf z}\) \(\newcommand{\rvec}{\mathbf r}\) \(\newcommand{\mvec}{\mathbf m}\) \(\newcommand{\zerovec}{\mathbf 0}\) \(\newcommand{\onevec}{\mathbf 1}\) \(\newcommand{\real}{\mathbb R}\) \(\newcommand{\twovec}[2]{\left[\begin{array}{r}#1 \\ #2 \end{array}\right]}\) \(\newcommand{\ctwovec}[2]{\left[\begin{array}{c}#1 \\ #2 \end{array}\right]}\) \(\newcommand{\threevec}[3]{\left[\begin{array}{r}#1 \\ #2 \\ #3 \end{array}\right]}\) \(\newcommand{\cthreevec}[3]{\left[\begin{array}{c}#1 \\ #2 \\ #3 \end{array}\right]}\) \(\newcommand{\fourvec}[4]{\left[\begin{array}{r}#1 \\ #2 \\ #3 \\ #4 \end{array}\right]}\) \(\newcommand{\cfourvec}[4]{\left[\begin{array}{c}#1 \\ #2 \\ #3 \\ #4 \end{array}\right]}\) \(\newcommand{\fivevec}[5]{\left[\begin{array}{r}#1 \\ #2 \\ #3 \\ #4 \\ #5 \\ \end{array}\right]}\) \(\newcommand{\cfivevec}[5]{\left[\begin{array}{c}#1 \\ #2 \\ #3 \\ #4 \\ #5 \\ \end{array}\right]}\) \(\newcommand{\mattwo}[4]{\left[\begin{array}{rr}#1 \amp #2 \\ #3 \amp #4 \\ \end{array}\right]}\) \(\newcommand{\laspan}[1]{\text{Span}\{#1\}}\) \(\newcommand{\bcal}{\cal B}\) \(\newcommand{\ccal}{\cal C}\) \(\newcommand{\scal}{\cal S}\) \(\newcommand{\wcal}{\cal W}\) \(\newcommand{\ecal}{\cal E}\) \(\newcommand{\coords}[2]{\left\{#1\right\}_{#2}}\) \(\newcommand{\gray}[1]{\color{gray}{#1}}\) \(\newcommand{\lgray}[1]{\color{lightgray}{#1}}\) \(\newcommand{\rank}{\operatorname{rank}}\) \(\newcommand{\row}{\text{Row}}\) \(\newcommand{\col}{\text{Col}}\) \(\renewcommand{\row}{\text{Row}}\) \(\newcommand{\nul}{\text{Nul}}\) \(\newcommand{\var}{\text{Var}}\) \(\newcommand{\corr}{\text{corr}}\) \(\newcommand{\len}[1]{\left|#1\right|}\) \(\newcommand{\bbar}{\overline{\bvec}}\) \(\newcommand{\bhat}{\widehat{\bvec}}\) \(\newcommand{\bperp}{\bvec^\perp}\) \(\newcommand{\xhat}{\widehat{\xvec}}\) \(\newcommand{\vhat}{\widehat{\vvec}}\) \(\newcommand{\uhat}{\widehat{\uvec}}\) \(\newcommand{\what}{\widehat{\wvec}}\) \(\newcommand{\Sighat}{\widehat{\Sigma}}\) \(\newcommand{\lt}{<}\) \(\newcommand{\gt}{>}\) \(\newcommand{\amp}{&}\) \(\definecolor{fillinmathshade}{gray}{0.9}\)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
- if \(a \mid b \) and \(a \mid c\) then \(a \mid (b+c)\).
- if \(a \mid b \) and \(a \mid c\) then \(a \mid (bc)\).
- 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\).