---
title: "divide"
type: concept
related: [Divide]
source: https://www.jemoka.com/posts/kbhdivide/
confidence: high
status: active
---

Let integer \(a,b \in \mathbb{Z}\), where \(b \neq 0\). We say \(b\) divides \(a\) (i.e. \(b|a\)) if there&rsquo;s some \(m \in \mathbb{Z}\) such that \(a = bm\).
additional information division algorithm Let \(a,b \in \mathbb{Z}\), \(b &gt; 0\). Then, there exists, uniquely, some \(q,r \in \mathbb{Z}\) such that \(a = bq + r\) with \(0 \leq r &lt;b\).
&ldquo;division with remainder&rdquo;
You will note that, if \(a &lt; b\), we can just say \(q = 0\).
Proof:
Existence Let us define some:
\begin{equation} S = \{a - bk: k \in \mathbb{Z}, a-bk \geq 0\} \end{equation}
We will note that this set is definitely non-empty:
If \(a \geq 0\), then \(a = a-b\cdot 0 \in S\) If \(a &lt; 0\) , then \(a-b(2a) = a(1-2b)\), we note that \(a &lt; 0\) and since \(b &gt;0\), \((1-2b) &lt;0\), so \(a(1-2b) &gt; 0\) and so \(a(1-2b) \in S\) So by the WOP, \(S\) has a smallest element. Let us, by WOP, define \(r\) to be the smallest element in \(S\).
Therefore, we can make some \(r = a-bq \in S\). We also know that \(r\) is non-negative, as that is the constraint of \(S\). Finally, we have to ensure that \(r\) is the actual remainder, we have to ensure that \(r &lt; b\).
Assume for contradiction \(r \geq b\). Then, \(r-b = (a-qb)-b = a-(q+1)b \geq 0\). Therefore, \(r-b \in S\). Yet, we said that \(r\) was the smallest element, reaching contradiction. Therefore, \(r&lt;b\) . \(\blacksquare\)
Uniqueness Let us have:
\begin{equation} a = bq+r = bq&rsquo; + r' \end{equation}
Recall that, \(0 \leq r &lt; b\). We desire that \(q = q&rsquo;\), \(r = r&rsquo;\).
WLOG let \(r \leq r&rsquo;\). So, \(0 \leq r&rsquo; - r\). Both \(r&rsquo;\) and \(r\) are remainders after dividing by \(b\), so \(r&rsquo; &lt; b\) and \(r &lt; b\). Therefore, we have:
\begin{equation} 0 \leq r&rsquo; - r &lt; b \end{equation}
Now, recall that:
\begin{align} &amp;bq+r = bq&rsquo; + r&rsquo;\\ \Rightarrow\ &amp;b(q-q&rsquo;) = r&rsquo; - r \end{align}
Now, we have that \(b|(r&rsquo; - r)\). Hence, we have some positive \(r&rsquo; - r\), which is smaller than b, but which is divisible by \(b\). This forces us to conclude that \(r&rsquo; - r = 0\).
Given \(r&rsquo; = r\), now, we can see that \(q = q&rsquo;\). \(\blacksquare\)
