next up previous contents
Next: The Euclidean algorithm Up: The integers Previous: Division   Contents

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$


next up previous contents
Next: The Euclidean algorithm Up: The integers Previous: Division   Contents
root 2002-06-10