0
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ Please add a link to the duplicate answer you've seen, and explain what it is you don't understand about it. $\endgroup$ – saulspatz Feb 27 at 10:42
  • $\begingroup$ 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. $\endgroup$ – Syed Feb 27 at 10:46
  • $\begingroup$ @Syed, have you applied Euclidean algorithm on $12n+3$ and $7n+1$? What did you get? $\endgroup$ – Ennar Feb 27 at 11:14
  • $\begingroup$ I got 1 as the answer $\endgroup$ – Syed Feb 27 at 11:14
  • $\begingroup$ But what about 9 and 3 $\endgroup$ – Syed Feb 27 at 11:15
1
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.