# 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$$

The argument is as follows:

1. We know there are integers $$q$$ and $$r$$ such that $$m=qn+r$$ and $$0\le r. 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 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$$.

• Thank you Gandalf! Let $m \leftarrow 51$, $n \leftarrow 20$. Any number that divides both $m$ and $n$ will also divide $m-qn = 51-2(20) = 51-40 = 11$. Ok, 11 is prime (not composite), so there is nothing to do here, right? Try it again with different numbers: Let $m \leftarrow 50$, $n \leftarrow 20$. $50-2(20) = 50-40 = 10$. There is a number that divides both $50$ an $20$, it is $10$ or $2$ (the set $\{10,2\}​$). Is my thinking write? Could you please shed light on why step 2 (analog to 3) always works? – Jonathan Komar Nov 8 '18 at 8:49
• The Euclidean Algorithm is an iterative process. In your first example you have shown that the greatest common divisor of $51$ and $20$ is either $1$ or $11$. In this case it is $1$ (i.e. $51$ and $20$ are coprime) but to show this you have to repeat the algorithm with $m=20$ and $n=11$. – gandalf61 Nov 8 '18 at 9:14