0
$\begingroup$

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$

$\endgroup$
1
$\begingroup$

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

$\endgroup$
2
  • $\begingroup$ 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? $\endgroup$ – Jonathan Komar Nov 8 '18 at 8:49
  • $\begingroup$ 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$. $\endgroup$ – gandalf61 Nov 8 '18 at 9:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.