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

Question

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 1

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$

Answer 2

I like to write this with a simple continued fraction as the middle step.

$$ \gcd( 3084, 1424 ) = ??? $$

$$ \frac{ 3084 }{ 1424 } = 2 + \frac{ 236 }{ 1424 } $$ $$ \frac{ 1424 }{ 236 } = 6 + \frac{ 8 }{ 236 } $$ $$ \frac{ 236 }{ 8 } = 29 + \frac{ 4 }{ 8 } $$ $$ \frac{ 8 }{ 4 } = 2 + \frac{ 0 }{ 4 } $$ Simple continued fraction tableau:
$$ \begin{array}{cccccccccc} & & 2 & & 6 & & 29 & & 2 & \\ \frac{ 0 }{ 1 } & \frac{ 1 }{ 0 } & & \frac{ 2 }{ 1 } & & \frac{ 13 }{ 6 } & & \frac{ 379 }{ 175 } & & \frac{ 771 }{ 356 } \end{array} $$ $$ $$ $$ \begin{array}{ccc} \frac{ 1 }{ 0 } & \mbox{digit} & 2 \\ \frac{ 2 }{ 1 } & \mbox{digit} & 6 \\ \frac{ 13 }{ 6 } & \mbox{digit} & 29 \\ \frac{ 379 }{ 175 } & \mbox{digit} & 2 \\ \frac{ 771 }{ 356 } & \mbox{digit} & 0 \\ \end{array} $$

$$ 771 \cdot 175 - 356 \cdot 379 = 1 $$

$$ \gcd( 3084, 1424 ) = 4 $$
$$ 3084 \cdot 175 - 1424 \cdot 379 = 4 $$