possible values of $\gcd{(5n+9,3n+3)}$ for every positive integer $n$

Question

I have tried to determine the values of $\gcd{(5n+9,3n+3)}$ for every positive integer n , but i'm not able to set all of them , I have took $a-b=\gcd{(a,b)}=2(n+3)$ then n+3|a-b then $a-b= (n+3) k$ , k is integer number then $\gcd{(a,b)}=(n+3)k$ , by this way it must give values for $k$ and $n$ , it's hard for me to get the possible values of $\gcd{(5n+9,3n+3)}$, Then Is there any possible way to get $\gcd{(5n+9,3n+3)}$ for every positive integer $n$?

Answer 1

If $d=\gcd{(5n+9,3n+3)}$ then $d|3n+3, 5n+9$ and hence $$d|(5n+9)-(3n+3)=2n+6 \\ d|3n+3-(2n+6)=n-3 \\ d|2n+6-2(n-3)=12$$

Now, for each potential value you have to check if you can find an $n$ such that the gcd is exactly that value.

Answer 2

Using repeatedly the identity $\gcd(a,b)=\gcd(b,a-b)$ we get:

$$\begin{align} \gcd(5n+9,3n+3)&=\gcd(3n+3,2n+6)\\ &=\gcd(2n+6,n-3)\\ &=\gcd(n-3,n+9)\\ &=\gcd(n+9,12) \end{align}$$

So this gcd is:

• $1$ if $n\equiv 2,4,8,10\pmod{12}$
• $2$ if $n\equiv 1,5\pmod{12}$
• $3$ if $n\equiv 0,6\pmod{12}$
• $4$ if $n\equiv 7,11\pmod{12}$
• $6$ if $n\equiv 9\pmod {12}$
• $12$ if $n\equiv 3\pmod{12}$