Euclidean Algorithm and Divison Algorithm on $\gcd(50+x^2,4x+2)=6$

Here's a mechanical way to compute the general gcd (when $\rm\color{#90f}{even}$) by the Euclidean algorithm.

Note $\, \color{#90f}2\mid (50+x^2,4x+2)\iff 2\mid 50+x^2\iff 2\mid x,\, $ so factoring $\,\color{#90f}2\,$ from our $\rm\color{#90f}{even}$ gcd

$$\ \ \begin{align} (50+x^2,4x+2) &= 2\,(25+x(x/2),\ 2x+1)\ \ \ \text{so scaling first arg by $\,\rm\color{#c00}{c=8}\ $ yields}\\ &= 2\,(200+(\color{#0a0}{2x})^2,\,\ 2x+1)\ \ \ \text{by $\,(\color{#c00}8,2x\!+\!1) = 1,$ see Remark below}\ \\ &= 2\,(200+(\color{#0a0}{-1})^2,\ 2x+1)\ \ \ \text{by $\,\color{#0a0}{2x\equiv -1}\!\!\!\pmod{\!2x\!+\!1}$}\\ &= 2\,(3\cdot 67,\ 2x+1)\\ &= 2\,(3,\,2x\!+\!1)\,(67,2x\!+\!1)\\ &= \bbox[5px,border:1px solid #c00]{2\,(3,\,x\!-\!1)\ (67,\,x\!-\!33)} \end{align}$$

which has a factor of $\,3\!\iff\! x\equiv 1\pmod{\!3},\,$ and a factor of $\,67\!\iff\! x\equiv 33\pmod{\!67},\,$ and, because $\,2\mid x\,$ these become $\,x\equiv 4\pmod{\!6}\,$ and $\,x\equiv 100\pmod{\!134}$.

Remark $ $ We used a slight generalization of the Euclidean algorithm which allows us to scale by integers $\,\color{#c00}c\,$ coprime to the gcd during the modular reduction step (above $\,\color{#c00}{c=8}),\,$ i.e.

$$(a,b)\, = \,(a,\,cb\bmod a)\ \ \ {\rm if}\ \ \ (a,c) = 1\qquad\quad\ \ $$

which is true since $\,(a,c)= 1\,\Rightarrow\, (a,\,cb\bmod a) = (a,cb) = (a,b)\ $ by Euclid.

Here is another example done this way, which explains how it can be viewed as applying a more general Polynomial Division Algorithm where the divisor is nonmonic (i.e. lead coef is not $1$).