2
$\begingroup$

Reading Lecture 5 here I found this proof for the long division remainder-based Euclid's GCD algorithm (page 20):

Given any two non-negative integers $a$ and $b$, we can obviously write $a = q·b +r$ for some non-negative quotient integer $q$ and some non-negative remainder integer $r$.

It follows directly from the form $a = q·b + r$ that every common divisor of $a$ and $b$ must also divide the remainder $r$.

[...]

Why is it that every common divisor of $a$ and $b$ must also divide the remainder $r$? I can't understand it.

$\endgroup$
  • 1
    $\begingroup$ BTW, that proof is awfully gappy. "We can obviously write" follows by chosing $q=0$ and $r=a$, which does not help us in any wy for the algorithm. The crucial step is that $0\le r<b$ can be quaranteed! This is an important property of the ring of integers that may not apply to other rings. $\endgroup$ – Hagen von Eitzen Apr 6 '13 at 16:37
4
$\begingroup$

If $d$ divides both $a$ and $b$, say $a=da'$ and $b=db'$, then $$ r = a-qb=da'-qdb'=d\cdot(a'-qb').$$

$\endgroup$
  • $\begingroup$ Simple, nice. It makes sense. Thanks :) $\endgroup$ – Alicia Apr 6 '13 at 17:10
1
$\begingroup$

It $t$ divides $a$ and $b$, then $t$ divides $a-qb$. But $a-qb=r$.

If you need full detail, let $a=ta'$ and $b=tb'$. Then $a-qb=t(a'-qb')$. So $t$ divides $a-qb$.

Remark: The calculation above holds whenever there is a decent notion of divisibility.

One should not underestimate the difficulty of the assertion that if $b$ is positive, there exist $q$ and $r$ such that $a=qb+r$ and $0\le r\le b-1$. True, it follows fairly quickly from the fact that every non-empty set of non-negative integers has a smallest element, or, equivalently, by induction.

The result about $q$ and $r$ generalizes nicely in only a restricted number of cases. For details, google Euclidean domain.

$\endgroup$
1
$\begingroup$

$\rm\begin{array}{rrl}{\bf Hint}\quad d\mid a,b\!\!\!\! &\Rightarrow&\!\!\!\rm a\equiv \,\color{#C00}0,\ b\equiv \,\color{#0A0}0\ \ \,(mod\ d)\\ &\Rightarrow&\!\!\!\! \begin{eqnarray}\rm r &\,=\:&\rm a-q\cdot b\\ &\,\equiv\:&\rm \color{#C00}0 -q\cdot \color{#0A0}0\,\equiv\, 0\ \ (mod\ d)\end{eqnarray}\\ &\Rightarrow&\rm\!\!\! d\mid r \end{array} $

$\endgroup$

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.