Proofs Involving Divisibility of Integers

Divides: if \(a, b \in \mathbb{Z}\) with \(a \neq 0\), we say "\(a\) divides \(b\)" if \(\exists c \in \mathbb{Z}: b = ac\).

  • We write \(a \mid b\).

  • We also say:

    • \(b\) is a multiple of \(a\).
    • \(a\) is a divisor of \(b\).

  • If \(a\) does not divide \(b\), we write \(a \nmid b\).

  • Old: \(ab\) even \(\iff a\) is even or \(b\) is even.

  • New: \(2 \mid ab \iff 2 \mid a \vee 2 \mid b\)

Result 4.1: let \(a, b, c \in \mathbb{Z}\) with \(a \neq 0\) and \(b \neq 0\).

  • If \(a \mid b\) and \(b \mid c\), then \(a \mid c\).
  • Proof:
    • Assume \(a \mid b\) and \(b \mid c\).
    • Then \(b = ax\) and \(c = by\), \(x, y \in \mathbb{Z}\).
    • We want to show that \(a \mid c\), meaning \(c = a \cdot \square, \square \in \mathbb{Z}\).
    • Observe:

\[ \begin{align} c = by = (ax)y = a(xy) \end{align} \]

  • So \(a \mid c\). \(\blacksquare\)

Result 4.3: let \(a, b, c, x, y \in \mathbb{Z}\), where \(a \neq 0\).

  • If \(a \mid b\) and \(a \mid c\), then \(a \mid (bx + cy)\).
  • Proof:
    • Assume \(a \mid b\) and \(a \mid c\), \(a \neq 0\).
    • Wrong: Then \(b = ax\) and \(c = ay, x, y \in \mathbb{Z}\).
      • We've already used \(x\) and \(y!\)
    • Then \(b = ar\) and \(c = as, r, s \in \mathbb{Z}\).
    • We want to show that \(a \mid (bx+cy\) meaning \(bx+cy = a \cdot \square, \square \in \mathbb{Z}\).
    • Observe:

\[ \begin{align} bx + cy &= (ar)x+(as)y\\ &= a(rx+sy) \end{align} \]

  • So \(a \mid (bx+cy)\). \(\blacksquare\)

Result 4.4: let \(x \in \mathbb{Z}\). If \(2 \mid (x-1)\), then \(4 \mid (x-1)\).

  • Proof:
  • Assume \(2 \mid (x^2-1)\).
    • So \(x^2 - 1 = 2y, y \in \mathbb{Z}\).
    • We want to show that \(4 \mid (x^2-1)\), meaning \(x^2-1 = 4 \cdot square, \square \in \mathbb{Z}\).
      • It's not clear what to do here!
      • That indicates that we probably need to try another path.
    • Try isolating the x term: \(x^2 = 2y+1\).
      • Notice: \(2y+1\) is odd, and we have a theorem saying that \(r^2\) odd \(\iff r\) odd!
      • This means \(x\) is odd.
    • So \(x = 2u+1, u \in \mathbb{Z}\).
    • Observe:

\[ \begin{align} x^2 - 1 &= (2u+1)^2-1\\ &= 4u^2+4u+1-1\\ &= 4(u^2+u) \end{align} \]

  • So \(4 \mid (x^2-1)\). \(\blacksquare\)

Result 4.5: Let \(x, y \in \mathbb{Z}\). If \(3 \nmid xy\), then \(3 \nmid x\) and \(3 \nmid y\).

  • Proof by Contrapositive
    • Assume \(~(3 \nmid x)\) and \(\neg 3\nmid y\)
      • \(3 \mid x\) or \(3 \mid y\).
    • So \(x = 3s\) or \(y = 3t\), \(s, t \in \mathbb{Z}\).
    • We want to show that \(3 \mid xy\), meaning \(xy = 3\square, \square \in \mathbb{Z}\).
    • WLOG, assume \(3\mid x\), meaning \(x = 3s\).
    • Observe: \(xy = (3s)y = 3(sy)\).
    • So \(3 \mid xy\).

Handy Observations: let \(n \in \mathbb{Z}\).

  1. \(n = 2q\) or \(n = 2q+1\), \(q \in \mathbb{Z}\).
  2. \(n = 3q\) or \(n = 3q+1\) or \(n = 3q+2\), \(q \in \mathbb{Z}\).
  3. For multiples of 2, we have 2 sets. Multiples of 3, 3 sets. Multiples of 4?
    • Notice the pattern :)

Result 4.6 let \(x \in \mathbb{Z}\).

  • If \(3 \nmid (x^2-1)\), then \(3 \mid x\).
  • Proof by Contrapositive:
    • Assume \(3 \nmid x\).
    • So \(x\) is not a multiple of 3.
    • So by the handy observation, \(x = 3q+1\) or \(x = 3q+2\), \(q \in \mathbb{Z}\).
    • We want to show that \(3 \mid (x^2-1)\), meaning \(x^2-1 = 3\square, \square \in \mathbb{Z}\).
      • Case 1: \(x = 3q+1\) \[ \begin{align} x^2-1 &= (3q+1)^2 - 1\\ &= 9q^2+6q+1-1\\ &= 3(3q^2+2q) \end{align} \]
        • So \(3 \mid (x^2 - 1)\).
      • Case 2: \(x = 3q+2\). \[ \begin{align} x^2 - 1 &= (3q+2)^2\\ &= 9q^2 + 12q + 4 - 1\\ &= 9q^2 + 12q + 3\\ = 3(3q^2+4q+1) \end{align} \]
        • So \(3 \mid (x^2-1)\).