<< elementary_number_theory

Divisibility

# Division Algorithm

For integer \(a,b\) with \(b\neq0\), there only exists two integer \(q,r\) which satisified \[ a = b \times q + r, \quad 0\leq r < b \] where \(q\) is quotient and \(r\) is remainder. \(q\) also named as partial quotient if \(r\neq0\).

Proof. First we prove the case when \(a, b > 0\).

(Existence) Let \(R = \{r ~|~ r = a-qb \ge 0, ~ q\in\mathbb{Z} \} \subset \mathbb{N}\), since \(a, b>0\), there must be at least one element that \(r = a - 0\times b = a > 0\), which inferred that \(R\) is a non-empty set of \(\mathbb{N}\), hence there must be a minimum number \(r \ge 0\).

Notice that the minimum \(r\) must less than \(b\). If not, we have \(a-qb \ge b\), so \(a-(q+1)b\ge 0\in R\), which contradicts to the statement that \(r\) is minimal.

(Uniqueness) Assume there’s another pair \((p', r')\) which satisfies the same condition:

\[ a = bq + r, \quad a = bq' + r', \qquad 0 \leq r,\ r' <b \] Thus, \[ b(q-q') = r-r' < b \Rightarrow q - q' < 1 \]

Since \(q, q'\) are both integer, this inequation implies that \(q=q'\) thus \(r=r'\), which concludes the uniqueness of pair \((p, r)\).

# Definition

For integer \(a, b\neq0\), if there exits an integer \(q\) which satisfies \[ a = bq \] We say that \(a\) divides \(b\), and \(a\) is a divisor or factor or \(b\), and \(b\) is a multiple of \(a\), denotes as \(a \ | \ b\).

# Property