The Euclidean Division

Proposition 6.2.18   Given $a$, $b \in \mathbb{N}$ there exists a unique pair of integers $(q,r) \in \mathbb{N}^2$ such that $a = q b + r$ and $0 \leq r < b$.

The number $q$ is called the quotient and the number $r$ is called the remainder in the division of $a$ by $b$.

Proof. Take $q$ the largest possible such that $q b \leq a$ and put $r = a - q b$. Then $0 \leq r < b$ since $a - qb \geq 0$ but $(q+1) b \ge a$. Now suppose that $a = q_1 b + r$ with $q_1$, $r_1 \in \mathbb{N}$ and $0 \leq r_1 < b$. Then $0 = (q - q_1) b + (r - r_1)$ and $b \mid r - r_1$. But $-b < r - r_1 < b$ so that $r = r_1$ and hence $q = q_1$. $\qedsymbol$

It is clear that $b \mid a$ if, and only if, $r = 0$ in the above.

Definition 6.2.19   Given $a$, $b \in \mathbb{N}$ then $d \in \mathbb{N}$ is the greatest common divisor of $a$ and $b$ if:

1. $d \mid a$ and $d \mid b$,
2. if $d' \mid a$ and $d' \mid b$ then $d' \mid d$ ( $d' \in \mathbb{N}$).

The greatest common divisor (henceforth gcd) of $a$ and $b$ is written $(a,b)$ or $\gcd (a,b)$. The gcd is obviously unique: if $c$ and $c'$ are both gcd's then they both divide each other and are therefore equal.

Theorem 6.2.20 (Existence of the gcd)   For $a$, $b \in \mathbb{N}$ $\gcd (a,b)$ exists. Moreover there exist integers $x$ and $y$ such that $(a,b) = a x + b y$.

Proof. Consider the set $I = \{ a x + b y : x,y \in \mathbb{Z}\wedge a x + b y > 0 \}$. Then $I \neq \emptyset$ so let $d$ be the least member of $I$. Now $\exists x_0, y_0$ such that $d = a x_0 + b y_0$, so that if $d' \mid a$ and $d' \mid b$ then $d' \mid d$. Now write $a = q d + r$ with $q$, $r \in \mathbb{N}_0$, $0 \le r < d$. We have $r = a - qd = a ( 1 - q x_0) + b( -q y_0)$. So $r = 0$, as otherwise $r \in I$: contrary to $d$ minimal. Similiarly, $d \mid b$ and thus $d$ is the gcd of $a$ and $b$. $\qedsymbol$

Lemma 6.2.21   If $a$, $b \in \mathbb{N}$ and $a = q b + r$ with $q$, $r \in \mathbb{N}_0$ and $0 \le r < b$ then $(a,b) = (b,r)$.

Proof. If $c \mid a$ and $c \mid b$ then $c \mid r$ and thus $c \mid (b,r)$. In particular, $(a,b) \mid (b,r)$. Now note that if $c \mid b$ and $c \mid r$ then $c \mid a$ and thus $c \mid (a,b)$. Therefore $(b,r) \mid (a,b)$ and hence $(b,r) = (a,b)$. $\qedsymbol$