Math Home
Number Theory

An integer \(a\) divides an integer \(b\) if there exists an integer \(c\) such that \[a \cdot c = b\] The notation is \(a|b\) and is read "\(a\) divides \(b.\) If \(a\) does not divide \(b,\) we write \(a \nmid b.\)

Examples: \(3|12\) since \(3 \cdot 4 = 12.\) However, \(3 \nmid 8\) since there is no integer \(c\) such that \(3 \cdot c = 8.\)

Properties: Let \(a, b,\) and \(c\) represent integers.

  1. \(a|a\) and \(a|-a\).
  2. If \(a|b\) and \(b|c\) then \(a|c.\)
  3. If \(a|b\) and \(a|c\) then \(a|(b+c)\).
  4. If \(a|b\) then \(a|(b+c)\) if and only if \(a|c.\)
▼ Proof:
  1. This is fundamental but trivial. \(a = 1 \cdot a\) and \(-a = -1 \cdot a.\)
  2. Since \(a|b\) there exists \(i\) such that \(a \cdot i = b.\) Since \(b|c\) there exists \(j\) such that \(b \cdot j = c.\) Substituting the first expression into the second, \((a \cdot i) \cdot j = c,\) or \(a \cdot (ij) = c,\) so \(a|c.\)
  3. By definition of divides, there exist integers \(i\) and \(j\) such that \(a \cdot i = b\) and \(a \cdot j = c.\) Substition gives the following: \begin{align} b + c & = a \cdot i + a \cdot j \\ & = a \cdot (i + j) \end{align} Since \(i + j\) is an integer, \(a | (b+c).\)

  4. One direction of the statement is just statement \(3.\) The reason for splitting up properties \(3\) and \(4\) this way is just for convenience when referencing them later. We only need to show that if \(a|b\) and \(a|(b+c),\) then \(a|c.\)

    By definition of divides, there exist integers \(i\) and \(j\) such that \(a \cdot i = b\) and \(a \cdot j = b+c.\) Rewrite \(c\) as \(-b + b + c\) and use substition as follows to show \(a|c:\) \begin{align} c & = -b + b + c \\ & = -(a \cdot i) + a \cdot j \\ & = a \cdot (-i + j) \end{align}