What thoughts should I be having when proving the Euclidean Division Algorithm? 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$
 A: The argument is as follows:


*

*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.

*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$.

*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$.

*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.

*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.)

*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$.
