Tuesday 28 May 2013

number theory - Why does $8$ not divide both the divisor and remainder?



The following is an explanation of why the division algorithm works for the two integers, $1424$ and $3084$. This is the link https://www.rit.edu/studentaffairs/asc/sites/rit.edu.studentaffairs.asc/files/docs/services/resources/handouts/DM6_EuclideanAlgorithm_BP_9_22_14.pdf





The example used to find the gcd$(1424, 3084)$ will be used to provide an idea
as to why the Euclidean Algorithm works. Let $d$ represent the greatest common
divisor. Since this number represents the largest divisor that evenly divides
both numbers, it is obvious that $d|1424$ and $d|3084$. Hence $d|3084 –1424$
in the same way that a numerator of two or more terms is divisible by a factor
in the denominator if and only if that factor divides evenly into each individual
term in the numerator. Furthermore $d|3084 – 2(1424)$ or, simplifying the left
side, $d|236$. Consequently we note that d divides the remainder resulting
from the division of the two numbers for which the greatest common factor is

being sought. This corresponds to the first long division calculated in the
example above.
The problem has now been reduced to a smaller one. We have that $d|1424$
and $d|236$. Hence $d|1424 – 236$, or better yet, $d|1424 – 6(236)$ which when
simplified reveals that $d|8$. At this point we know that d must be one of the
following values: $1, 2, 4,$ or $8$. Note that $8$ is the remainder resulting from the
division of the divisor and remainder found in the original division, so it will
not be a divisor of both. So we will take the divisor and remainder from the
second division to reduce the problem to yet an even smaller one.





My question is, why is it that because $8$ is the remainder resulting from the
division of the divisor and remainder found in the original division, that it is not a divisor of both?


Answer



The Euclidean algorithm stops when the remainder divides both divisor and quotient (which is thus shown to be the $\gcd$). So the statement that you question is odd, unless it is referring to some context outside the scope of the text and the link. Still it is certainly true that at any point in the process, the $\gcd$ is one of the factors of the latest remainder.



I write the extended Euclidean algorithm as a table:



$\begin{array}{c|c}
n & s & t & q \\ \hline

3084 & 1 & 0 & \\
1424 & 0 & 1 & 2 \\
236 & 1 & -2 & 6 \\
8 & -6 & 13 & 29 \\
\color{red}{4} & 175 & -379 & 2 \\
0 & -356 & 771 & 0 \\
\end{array}$



... each line solving the equation $n=3084\cdot s + 1424 \cdot t$, set up in the first two lines with the trivial equations for $n=3084$ and $1424$, and then subtracting $q$ times the line from the line above to get the smaller $n$ value on the next line. The last non-zero $n$ is the $\gcd$ of the opening pair.




This also gives the appropriate Bézout's identity for the original pair for a linear combination that gives their $\gcd$: $175\cdot 3084+(-379)\cdot 1424=4$


No comments:

Post a Comment

real analysis - How to find $lim_{hrightarrow 0}frac{sin(ha)}{h}$

How to find $\lim_{h\rightarrow 0}\frac{\sin(ha)}{h}$ without lhopital rule? I know when I use lhopital I easy get $$ \lim_{h\rightarrow 0}...