How to prove that $\gcd(2n+3, 3n+1)$ divides $7$?

Question

How can I start proving that gcd(2n+3, 3n+1) | 7?

EDIT: It is $\gcd(2n+3, 3n+1)$ divides $7$. My bad. Thanks paw88789.

Answer 1

$$\gcd(2n+3, 3n+1) = \gcd(n-2, 3n+1) = \gcd(n-2, 7) \mid 7$$

Answer 2

As to the problem $gcd(2n+3,3n+1)|7$ we shall use the euclidean algorithm.

So $3n+1=2n+3+(n-2)$

$(2n+3)=2(n-2)+7$

So a divisor of $3n+1$ and $2n+3$ must divide $7$

Answer 3

As $(a,b)$ must divide $ax+by$ for integers $x,y$

$(2n+3,3n+1)$ must divide $3(2n+3)-2(3n+1)=7$

The idea in such problems is to eliminate the variable $(n)$

Answer 4

By Euclid theorem GCD(2n+3,3n+1)=a(2n+3)+b(3n+1) =>GCD(2n+3,3n+1)=n(2a+3b)+(3a+b)----------eqn1

To find Gcd n coefficient equate to zero. 2a+3b=0 =>a/b=-3/2

Take minimum values for a and b a=3 and b=-2 Substitute in eqn1 GCD(2n+3,3n+1)=n(0)+(3*3-2) GCD(2n+3,3n+1)=7 Hence proved.