Integer Division Theorem

Dependencies: None

Let $a$ and $b$ be integers, with $b$ > 0. Then there exist unique integers $q$ and $r$ such that $a=b\ast q+r$ and $0\le r<b$.

$r$ is denoted as $a\mathrm{\%}b$ and $q=\lfloor \frac{a}{b}\rfloor$.

Proof

Let $S=\{a-bk:k\in \mathbb{Z}\text{ and }a-bk\ge 0\}$.

If $a>0$, $S$ is non-empty for $k=0$. If $a\le 0$, $S$ is non-empty for $k=2a$. Since $S$ is a non-empty set of non-negative integers, $S$ has a smallest element.

Let $r=minS$. Then $\mathrm{\exists }q$ such that $r=a-bq$. Assume (for proof by contradiction), that $r\ge b$. Then $r-b=a-(b+1)q\in S$. Since $r-b<r$ and $r=minS$, we have a contradiction.

Hence, our assumption was wrong, so $0\le r<b$. This proves the existence of $q$ and $r$.

Let $a=b{q}_1+r_1=b{q}_2+r_2$. Then $b(q_1-q_2)=(r_2-r_1)\Rightarrow b\text{ divides }(r_2-r_1)$. $r_2-r_1=0$ is the only possibility because $-(b-1)\le r_2-r_1\le (b-1)$. Therefore, $r_1=r_2$ and $q_1=q_2$. This proves the uniqueness of $q$ and $r$.

$$r<b\Rightarrow \frac{r}{b}<1\Rightarrow \lfloor \frac{r}{b}\rfloor =0$$

$$\lfloor \frac{a}{b}\rfloor =\lfloor \frac{bq+r}{b}\rfloor =\lfloor q+\frac{r}{b}\rfloor =q+\lfloor \frac{r}{b}\rfloor =q$$

Dependency for:

1. Product of coprime divisors is divisor
2. ϕ is multiplicative
3. LCM divides common multiple
4. GCD is the smallest Linear Combination Used in proof
5. Order of cyclic subgroup is order of generator
6. Zn is a ring
7. Every ideal of Z is a principal ideal

Info:

• Depth: 0
• Number of transitive dependencies: 0

Transitive dependencies: None