\(d\) divides \(n\) (in \(\mathbb Z\) ) means \(n=kd\) for some \(k\in \mathbb Z\). We denote it by \(d\vert n\). For example, \(2\vert 8\) and \(2\nmid 9\).
Observation.
Let \(a\), \(b\), and \(c\) be integers.
If \(a\vert b\) and \(b\vert c\), then \(a\vert c\).
If \(a\vert b\) and \(a\vert c\), then \(a\vert (bx+cy)\) for all integers \(x\) and \(y\).
Proof.
Suppose \(a\vert b\) and \(b\vert c\). Then \(b=ra\) and \(c=sb\) for some integer \(r\) and \(s\). So \(c=sb=s(ra)=(sr)a\) is divisible by \(a\).
Suppose \(a\vert b\) and \(a\vert c\). Then \(b=ra\) and \(c=sa\) for some integer \(r\) and \(s\). So for any integers \(x\) and \(y\), \(bx+cy=rax+say=(rx+sy)a\) is divisible by \(a\). ◼
Other divisibility properties can be obtained similarly. Proposition.
The following are true for all integers \(a\) and \(b\).
If \(a\vert b\), then \(a\leq |a|\leq |b|\).
If \(a\vert b\) and \(b\vert a\), then \(a=\pm b\).
Theorem. (Division Theorem)
For given two integers \(a\) and \(b\) where \(b>0\), we can write \(a=bq+r\) for some unique integers \(q\) and \(r\) where \(0\leq r< b\).
Proof. If \(b\vert a\), then \(q=a/b\) and \(r=0\). Suppose \(b\nmid a\). Let
\[S=\{a-kb\;|\;k\in \mathbb Z \text{ such that } a-kb> 0\}.\] Note that \(S\subseteq \mathbb N\). Note \(a-(-1-|a|)b\geq b>0\). So \(a-(-1-|a|)b\in S\) and thus \(S\neq \varnothing\). By the well-ordering principle (every non-empty set of positive integers contains a least element) \(S\) has a smallest element, say \(r\). Then \(r=a-qb>0\) for some \(q\in \mathbb Z\). So \(a=bq+r\).
Now we show \(r< b\). If \(r=b\), then \(a=bq+b=(q+1)b\) is divisible by \(b\), a contradiction. Let \(r> b\). Then \(a-(q+1)b=(a-qb)-b=r-b>0\). So \(r-b\in S\) contradicting that \(r\) is the smallest element in \(S\). Thus \(r< b\).
To show uniqueness of \(q\) and \(r\), suppose \(a=bq'+r'\) for some unique integers \(q'\) and \(r'\) where \(0\leq r'< b \). Then \[a-a=(bq+r)-(bq'+r') \implies 0=b(q-q')+(r-r') \implies r'-r=b(q-q').\] Since \(0\leq r'< b\) and \( -b <-r\leq 0\), we have \( -b < r'-r < b \). Since \(r'-r=b(q-q')\), \(-b < b(q-q')< b \) which implies \( -1< q-q'<1 \). Thus \(q-q'=0\), i.e., \(q=q'\). Consequently \(r=r'\).
◼
For \(a=bq+r\) in the Division Theorem, \(q\) and \(r\) are called the quotient and the remainder respectively. It can be verified that \(q=\lfloor\frac{a}{b}\rfloor\), the greatest integer less than or equal to \(\frac{a}{b}\) and \(r=a-b\lfloor\frac{a}{b}\rfloor\).
Example.
For \(a=-163\) and \(b=5\), \(q=\lfloor \frac{a}{b}\rfloor=\lfloor -32.6\rfloor=-33\) and \(r=a-b\lfloor \frac{a}{b}\rfloor=-163-5(-33)=2\). Verify that \(-163=5\cdot (-33)+2\).