Proofs Involving Congruence of Integers

Motivation

Let \(x, y \in \mathbb{Z}\).

  • \(n = 2\): \(x, y\) must have the form \(2q\) or \(2q+1, q \in \mathbb{Z}\).
    • Observe: \(x - y = \{2a-2b, (2a+1) - (2b+1)\} = 2(a-b)\).
  • \(n = 3\): \(x, y\) must have the form \(3q, 3q+1, 3q+2, q \in \mathbb{Z}\).
    • Observe: \(x - y = \{3a-3b, (3a+1)-(3b+1), (3a+2)-(3b+2)\} = 3(a-b)\).

For \(a, b, n \in \mathbb{Z}, n \geq 2\), we say \(a\) is congruent to \(b \pmod n\) written \(a \equiv b \pmod n\)

  • "\(a\) equals \(b\) \(\pm\) a multiple of \(n\)"
    • means \(n \mid (a-b)\).

New Interpretation: \(x \in \mathbb{Z}\).

  • \(x = 2q\) or \(x = 2q+1, q \in \mathbb{Z}\).
  • \(x \equiv 0 \pmod 2\) or \(x \equiv 1 \pmod 2\).

Result 4.9: let \(a, b, k, n \in \mathbb{Z}, n \geq 2\).

  • If \(a \equiv b \pmod n\), then \(ka \equiv kb \pmod n\).
  • Proof:
    • Assume \(a \equiv b \pmod n\).
    • This means \(n \mid (a - b)\).
    • Hence \(a - b = nx, x \in \mathbb{Z}\).
    • We want to show that \(ka \equiv kb \pmod n\), meaning \(n \mid (ka - kb)\)
      • hence \(ka - kb = n\square, \square \in \mathbb{Z}\).
    • Observe:

\[ \begin{align} ka - kb &= k(a - b)\\ &= k(nx)\\ &= n(kx) \end{align} \]

  • Thus \(ka \equiv kb \pmod n\). \(\blacksquare\)

Result 4.10: let \(a, b, c, d, n \in \mathbb{Z}, n \geq 2\).

  • If \(a \equiv b \pmod n\) and \(c \equiv d \pmod n\)
  • Then \(a + c \equiv b + d \pmod n\)
  • Proof:
    • Assume \(a \equiv b \pmod n\) and \(c \equiv d \pmod n\).
      • meaning \(n \mid (a-b)\) and \(n \mid (c-d)\)
    • Hence \(a - b = nx\) and \(c - d = ny, x, y \in \mathbb{Z}\)
    • We want to show that \(a + c \equiv b+d \pmod n\), meaning \(n \mid \left[(a+c)-(b+d)\right]\)
    • Observe:

\[ \begin{align} (a + c) - (b + d) &= (a - b) + (c - d)\\ &= nx + ny\\ &= n(x + y) \end{align} \]

  • So \(a + c \equiv b + d \pmod n\)

Result 4.11: let \(a, b, c, d, n \in \mathbb{Z}, n \geq 2\).

  • If \(a \equiv b \pmod n\) and \(c \equiv d \pmod n\)
  • Then \(ac \equiv bd \pmod n\).
  • Proof: Assume \(a \equiv b \pmod n\) and \(c \equiv d \pmod n\).
  • So, \(a - b = nx\) and \(c - d = ny, x, y \in \mathbb{Z}\).
  • We want to show that \(ac \equiv bd \pmod n\), so \(ac-bd = n\square, \square \in \mathbb{Z}\).
    • we have \(a = b+nx\) and \(c = d+ny\)
  • Observe:

\[ \begin{align} ac-bd &= (b+nx)(d+ny)-bd\\ &= bd+bny + nxd + nxny - bd\\ &= n(by+xd+xny) \end{align} \]

  • So \(ac \equiv bd \pmod n\). \(\blacksquare\)

Result 4.12: let \(n \in \mathbb{Z}\).

  • If \(n^2 \not\equiv n \pmod 3\)
  • then \(n \not\equiv 0 \pmod 3\) and \(n \not\equiv 1 \pmod 3\)
    • For equals:
      • \(n^2 \neq n \implies [n \neq 0 \wedge n \neq 1]\) means \([n = 0\) or \(n = 1] \implies n^2=n\)
  • Proof by Contrapositive
    • Assume \(\neg[n \not\equiv 0 \pmod 3]\) and \(n \not\equiv 1 \pmod 3\).
      • \(n \equiv 0 \pmod 3\) OR \(n \equiv 1 \pmod 3\).
    • We want to show that \(n^2 \equiv n \pmod 3\), so \(n^2 - n = 3\square, \square \in \mathbb{Z}\).
    • Case 1: \(n \equiv 0 \pmod 3\)
      • So \(n - 0 = 3k, k \in \mathbb{Z}\).
      • Observe: \(n^2 - n = (3k)^2-(3k) = 3(3k^2-k)\).
      • So \(n^2 \equiv n \pmod 3\).
    • Case 2: \(n \equiv 1 \pmod 3\).
      • So \(n - 1 = 3j, j \in \mathbb{Z}\).
        • \(n = 1+3j\).
      • Observe: \[ \begin{align} n^2-n &= (1+3j)^2 - (1+3j)\\ &= 1 + 6j + 9j^2 - 1 -3j\\ &= 3(2j+3j^2-j) \end{align} \]
      • So \(n^2 \equiv n \pmod 3\).