What thoughts should I be having when proving the Euclidean Division Algorithm?

Question

Given $m > 0 \mathbin{|} m ∊ ℕ$ and $n > 0 \mathbin{|} m ∊ ℕ$, let's say

$m \leftarrow 50$

$n \leftarrow 20$

Number Theory tells us that any positive integer can be written as a product of two other integers and remainder $r$, where $r=0$ or $r>0$, right?

How do I understand the following statements? (How can a number divide an equation?)

• Any number that divides $\{m,n\}$ must divide $m - qn = r$.

• Any number that divides $\{n,r\}$ must divide $qn + r = m$.

How do I conclude the following?

Therefore, the set of divisors that divide $\{m,n\}$ are the same as the set of divisors that divide $\{n,r\}$, in particular, the greatest divisor in both of those sets will be (must be) the same.

I ask this because I am pretty sure that the conclusion above is the core of the whole proof, yet I am not as mathematically talented as many others, because I am not at a point where I can confidently explain this to someone else.

---

Plugging in the numbers:

• $50 - (2)20 = 10$ as $m - qn = r$

• $(2)20 + 10 = 50$ as $qn + r = m$

Answer 1

The argument is as follows:

1. We know there are integers $q$ and $r$ such that $m=qn+r$ and $0\le r<n$. If $r=0$ then $m=qn$ so the greatest divisor of $m$ and $n$ is $n$ and we are done. But if $r > 0$ we can proceed as follows.

2. Any number that divides both $m$ and $n$ will also divide $m-qn$. But $m-qn=r$. So any number that divides both $m$ and $n$ also divides $r$.

3. Any number that divides both $n$ and $r$ will also divide $qn+r$. But $qn+r=m$. So any number that divides both $n$ and $r$ also divides $m$.

4. Suppose $S$ is the set of numbers that divide both $m$ and $n$. Suppose $T$ is divide both $n$ and $r$. (2) shows that if $s \in S$ then $s \in T$, so $S \subset T$. (3) shows that if $t \in T$ then $t \in S$, so $T \subset S$. Since $S \subset T$ and $T \subset S$, the sets $S$ and $T$ must be the same set.

5. Since $S=T$, we can conclude that $\max(S) = \max(T)$. In other words, the greatest divisor of $m$ and $n$ is also the greatest divisor of $n$ and $r$. (Actually, there is one small step missing here - we must show that $S$ is not the empty set, so that it actually has a maximum. But we know for certain that $1$ divides any integer, so $1 \in S$, so $S$ is not empty.)

6. Now repeat the argument replacing $m$ and $n$ with $n$ and $r$. Since $r<n$ we are reducing the size of the numbers with each iteration. Eventually the process must finish at step (1) with $r=0$, and we have found the greatest divisor of the original $m$ and $n$.