Number Theory Home

## Divisibility in $$\mathbb Z$$

$$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.

1. If $$a\vert b$$ and $$b\vert c$$, then $$a\vert c$$.

2. If $$a\vert b$$ and $$a\vert c$$, then $$a\vert (bx+cy)$$ for all integers $$x$$ and $$y$$.

Proof.
1. 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$$.
2. 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$$.

1. If $$a\vert b$$, then $$a\leq |a|\leq |b|$$.

2. 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$$.

Last edited