calculate $\mathrm{gcd}(10n+3,5n+2)$

Question

Is this a correct solution?

Show that if $n\in\mathbb{Z}$ then $(10n+3,5n+2)=1$. $(a,b)$ being the greatest common divisor.

We can use the Eucledean algorithm to get $$ 10n+3=1\cdot(5n+2)+5n+1 $$ $$ 5n+2=1\cdot(5n+1)+1 $$ $$ 5n+1=(5n+1)\cdot 1+0 $$ and we see that the last nonzero remainder is $1$ therefore $(10n+3,5n+2)=1$. Is there a more elegant solution?

Thank you!

Answer 1

$(-1)(10n+3)+(2)(5n+2)=1$ So $\gcd(10n+3,5n+2)=1$ by Bezout's Lemma.

Answer 2

Yours looks good. Here is a similar approach (even shorter):$$(2)(5n+2)+(-1)(10n+3)=1$$ Hence, by the fact that $$\gcd(x,y)=1\iff \exists u,v\in\Bbb Z:ux+vy=1$$we have $\gcd(5n+2,10n+3)=1$.

Answer 3

If integer $d>0$ divides both $10n+3,5n+2;$

$d$ must divide $$10n+3-2(5n+2)=-?$$

The idea is to eliminate $n$

Answer 4

Let d = (10n+3,5n+2) so d|(10n+3) and d|(5n+2). So 10n+3 = dx and 5n+2 = dy for some integers x and y. We can write 2*(5n+2) = 10n+4 = d*(2y) and (10n+4) - (10n+3) = 1 = d(2*y-x). Then d|1 and d ${\leq}$ 1 but by definition d, the gcd, is a positive integer so it must be ${\geq}$ to 1. So by the Squeeze Thm d must be equal to 1.