Using GCD with remainder to list all the integer elements in the set

My question is:

For an integer k, define $f(x) = gcd (13x + 2, 5x − 1)$, use GCD With Remainders to list all the elements in the set ${f(x): x ∈ Z}$.

I divided 13x+2 by 5x-1 first, and got a quotient of 13/5 and a remainder of 23/5. But I am confused because GCDWR only works for integers. Therefore, if I write the next step as $gcd (5x-1, 23/5)$, that would be violating the rules for GCDWR. Could anyone give me a hint on how to proceed in the correct way? Greatly appreciated!

Solution 1:

This gcd is computable purely mechanically by a slight generalization of the Euclidean algorithm which allows us to scale by integers $\,c\,$ coprime to the gcd during the modular reduction step, i.e.

Lemma $\, \ \ \quad\qquad\qquad\bbox[8px,border:1px solid #c00]{(a,b)\, = \,(a,\,cb\bmod a)\ \ \ {\rm if}\ \ \ (a,c) = 1}\qquad\qquad $

which is true since $\,(a,c)= 1\,\Rightarrow\, (a,\,cb\bmod a) = (a,cb) = (a,b)\ $ by Euclid. When computing the gcd of polynomials $\,f(x),g(x)$ with integer coef's, we can use such scalings to force the lead coef of the dividend to be divisible by the lead coef of the divisor, which enables the division to be performed with integer (vs. fraction) arithmetic. Let's do that in the example at hand.

$$\ \ \begin{align} (5x\!-\!1,\, 13x\!+\!2) &= (5x\!-\!1,\,13(\color{#c00}{5x})\!+\!10)\ \ \ \text{by Lemma: scale 2nd arg by $\,\rm\color{#c00}{c=5}$}\\[.2em] &= (\color{#0a0}5x\!-\!1,\,23)\ \ \ {\rm by}\ \ \color{#c00}{5x\equiv 1}\!\!\!\pmod{5x\!-\!1}\\[.2em] &= (x\!-\!14,\,23)\ \ \ \text{by Lemma: scale 1st arg by $\,\color{#0a0}{5^{-1}\!\equiv 14}\!\!\!\!\pmod{\!23}$} \end{align}\qquad$$

Thus, since $\,23\,$ is prime, the gcd $= 1\,$ if $\,23\nmid x\!-\!14,\,$ else the gcd $= 23$.

Remark $ $ 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 $\neq 1$), and here is another one.

There are many ways to compute the modular inverse $\,1/5 = 5^{-1}\pmod{23},\,$ e.g.

$\bmod{23}\!:\,\ \color{#0a0}{\dfrac{1}5} \equiv \dfrac{5}{25}\equiv \dfrac{28}2\equiv \color{#0a0}{14}\ $ by Gauss's Algorithm.