Skip to main content
\(\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}}\)
Mathematics LibreTexts

2.4 Arithmetic of divisibility

  • Page ID
    7428
  • [ "stage:draft", "article:topic", "authorname:thangarajahp", "license:ccbyncsa", "showtoc:yes" ]

    \( \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?