2. Division Algorithm

Calculating the greatest common divisor of two large numbers make take too much time without a proper algorithm. The following algorithm is central in number theory because it provides an important characteristic of the greatest common divisor

Theorem: (The division algorithm) Given positive integers, $a,b$ with $b \neq 0$, there exist unique $q$ and $r$ such that $a = qb +r$ with $0 \leq r < b$.
Proof) Let $S = \{ a - qb ~|~ q \in \mathbb{Z}\} \cap \mathbb{Z}^{\geq 0}$, then we have $a \in S$, so the set $S$ is nonempty. $\mathbb{Z}^{\geq 0}$ is the set of all non-negative integers. Also $S$ is bounded below $0$ because by our construction. By the well-ordering principle, there exists a minimal element $a-qb$ for some $q \in \mathbb{Z}$. Let $r = ab-q$ and suppose $r \geq b$, then we have $ab - q \geq b \Rightarrow a(b-1) -q \geq 0$, hence $a(b-1) - q \in S$ which contradicts the minimality of $r$. Hence $0 \leq r < b$. Now for uniqueness, consider if there exist two pairs $(q_1, r_1), (q_2, r_2)$ such that

$a= q_1 b + r_1$

$a= q_2 b +r_2$

By subtracting the two equations, we get $(q_1 - q_2)b + (r_1 - r_2) = 0$. This implies that $b | (r_1 - r_2)$. Because $0 \leq r_1, r_2 < b$, we see that $-b < r_1 - r_2 < b$, hence in order for $b$ to divide $r_1 - r_2$, $r_1 - r_2$ has to equal to $0$, hence $r_1 = r_2$. Then we have $(q_1 - q_2) b = 0$. Since we have assumed $b \neq 0$, $q_1 - q_2 = 0 \Rightarrow q_1 = q_2$.

The same result holds for any two integers not both zero by generalizing into the following form:

Theorem: (Generalization) Given two integers $a,b$ with $b \neq 0$, there exist unique $q$ and $r$ such that $a=qb+r$ with $0 \leq r < |b|$.

Proof) Exercise for the reader.

Sidenote[Skip this note if you have not taken abstract algebra]: For those who will be taking (have taken) abstract algebra, the ring of integers $\mathbb{Z}$ becomes a euclidean domain. Then the unique factorization theorem comes by the fact that the euclidean domain is a UFD(unique factorization domain), or more strongly a PID(Principal Ideal Domain).

As mentioned above, the division algorithm provides an easier way to compute the greatest common divisor of two pairs which is stated as the following lemma:

Lemma: If $a=bq+r$, then $gcd(a,b) = gcd(b,r)$.

Proof) Let $d= gcd(a,b)$ then $d|b$ and $d|a$ hence $d| a-bq = r$ from the lemma of the previous post. Thus $d$ satisfies the first property of the greatest common divisor for $b$ and $r$. Suppose we have $c|b$ and $c|r$, then $c| bq + r = a$, hence $c | gcd(a,b) = d$, hence $c \leq d$. By the uniqueness of the greatest common divisor, we see that $d=gcd(b,r)$. 

Without loss of generosity, we may assume that $a \geq b$, then as $r < |b|$ we are given  a new pair of integers $(b,r)$ that are "smaller" than the original pair $(a,b)$. Continuing the process, we are given with two pairs that are multiple of each other and the divisor becomes the divisor of the original pair. Which can be stated as follows:

Theorem: (The Euclidean Algorithm) Let $a,b \in \mathbb{Z}$ with $b \neq 0$, then apply division algorithm recursively will give

$a = bq + r$

$b = rq_0 + r_1$

$r = r_1q_1 + r_2$

$\vdots$

Then there exists $k$ such that the remainder is $0$ 

$r_k = r_{k+1}q_{k+1}$

Then $gcd(a,b) = gcd(r_k, r_{k+1}) = r_{k+1}$.

Proof) We have sequence of positive numbers $|b| > r_0 > r_1 > \cdots$, then after applying at most $|b|$-times, we see that the remainder has to be $0$ at some point. (i.e. the process ends). Then by the lemma above we have $gcd(a,b) = gcd(b, r_0) = gcd(r_0, r_1) = \cdots gcd(r_k, r_{k+1}) = r_{k+1}$ as $r_{k+1} | r_k$.

Theorem: If $gcd(a,b) = d$, then there exist integers $x,y$ such that $ax+by = d$.

Proof) We reverse the euclidean algorithm. Then observe that $r_{k+1}$ is a linear combination of $r_k$ and $r_{k-1}$, then by induction we can show that $r_{k+1}$ is a linear combination of $a$ and $b$. The detail is omitted is because the proof is tedious.

Corollary: Let $a$ and $d$ be relatively prime, then $d|ab$, then $d|b$.

Proof) Because $gcd(a,d) = 1$, there exist $x,y$ such that $ax + dy = 1$, then multiplying $b$ on both side, we get $abx + dby = b$, then because $d| ab$ and $d|d$, we see that $d | abx + dby = b$.

Corollary: Let $gcd(a,b) = d$, and suppose $c|a$ and $c|b$ then $c|d$. 

Proof) There exist $x, y \in \mathbb{Z}$ such that $ax + by = d$, then by the assumption we clearly see that $c| ax+by = d$.

Corollary: Let $a|m$ and $b|m$ with $a$ and $b$ be relatively prime, then $ab|m$.

Proof) There exists $q$ such that $aq = m$. By the previous corollary, $b|m = aq$ implies that $b|q$ as $gcd(a,b) = 1$, hence there exists $r$ such that $q = br$, i.e. $abr= m$. As a result, $ab | m$.