Euclidean Algorithm and Divison Algorithm on $\gcd(50+x^2,4x+2)=6$ Recently, this question was asked: Finding smallest x for gcd(50+x2,4x+2)=6. The question is essentially in the title, and I posted a solution but I'm not confident about it (and so I deleted it). It's this:
We know that the gcd of those two terms $50+x^2,4x+2$ must be equal to the gcd of their remainder when $50+x^2$ is divided by $4x+2$, which is $201/4$. So, $\gcd{(4x+2,201/4)}=6$. I thought I could multiply $201/4$ by $4$ because $4x+2$ is not divisible by $4$, but then I realized that it is divisible by $2$, and therefore I cannot multiply. I would like to continue this solution along this path. How can I do so? 
 A: 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$).
