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

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.

• Please add a link to the duplicate answer you've seen, and explain what it is you don't understand about it. – saulspatz Feb 27 at 10:42
• math.stackexchange.com/questions/3123968/… This is the same question asked by another user and it have been marked as duplicate but the duplicate answers use some other method and i am looking for proof by Euclidean Algorithm. – Syed Feb 27 at 10:46
• @Syed, have you applied Euclidean algorithm on $12n+3$ and $7n+1$? What did you get? – Ennar Feb 27 at 11:14
• I got 1 as the answer – Syed Feb 27 at 11:14
• But what about 9 and 3 – Syed Feb 27 at 11:15

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\}$$.
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$$.