Prove that $\{\gcd(12n + 3, 7n + 1) : n \in \Bbb Z\} = \{1, 3, 9\}.$

Question

Prove that $\{\gcd(12n + 3, 7n + 1) \vert\ n \in \Bbb Z\} = \{1, 3, 9\}.$

I just don't know how to proceed with this proof. I have seen a duplicate answer by Bill and Macy here but I am still confused. Any help would be appreciated.

Answer 1

In the spirit of the Euclidean algorithm:$$\begin{array}.\gcd(12n+3, 7n+1)&=\gcd(5n+2, 7n+1)\\&=\gcd(5n+2, 2n-1)\\&=\gcd(n+4, 2n-1)\\&=\gcd(n+4, -9)\end{array}$$

You see that the $\gcd$ has to divide $9$, but apart from that there are no constraints since $n$ can be any integer. Therefore the set of possible values is $\{1,3,9\}$.

Answer 2

The extended Euclidean algorithm gives $$ 9 = 7(12n+3)-12(7n+1) $$ Therefore, every common divisor of $12n+3$ and $7n+1$ must divide $9$.