Find $\gcd(5n+3,3n+2)$, $n\in \Bbb{Z}, n\ge 1$. I don't know where to start. First two questions were: a. Prove $\gcd(a,b,c)=\gcd(\gcd(a,b),c)$. b. Prove $\gcd(ab+c,a)=\gcd(c,a)$. Maybe it has something to do with it. I would appreciate your help.
$\endgroup$ 12 Answers
$\begingroup$HINT:
Observe that $$5(3n+2)-3(5n+3)=1$$
The idea is to eliminate $n$ and to find a constant
and use the fact that $(a,b)|(ax+by)$ where $x,y$ are integers
$\endgroup$ 4 $\begingroup$Note that, if $a>b$, then $\gcd (a,b) = \gcd (b, a-b)$. Then $\gcd (5n+3,3n+2) = \gcd (3n+2,2n+1) = \gcd (2n+1,n+1) = \gcd (n+1,n) = \gcd (n,1) = 1$.
$\endgroup$ 4
