Find all possible values of GCD(4n + 4, 6n + 3) for naturals n and prove that there are no others
3·(4n + 4) - 2·(6n + 3) = 6, whence the desired GCD is a divisor 6. But 6n + 3 is odd, so only 1 and 3 remain. n=1 and n=2 are examples for GCD=1 and GCD=3
is the solution correct ?
any other way to solve this ?
This is correct. A slightly different way to solve it is by observing that $$ (4n+4,6n+3) = (4n+4,2n-1) = (6,2n-1) = (3,2n-1). $$
Your way is correct.
Other way.
$\gcd(4n+4, 6n+3) = \gcd(4n+4, (6n+3) - (4n+4)) =$
$\gcd (4n+4, 2n -1) = \gcd(4n+4 - 2(2n-1), 2n-1)=$
$\gcd (6, 2n- 1) = $
... Now two things should be apparent. $2n-1$ is odd and $6$ is even so the prime factor $2$ of $6$ will not be a factor of $2n-1$. And Lemma: if $\gcd(j,b) = 1$ then $\gcd(j*a, b) = \gcd(a,b)$. That can be easily proven many ways.
So $\gcd(2*3, 2n-1) = \gcd(3,2n-1)$. Which is equal to $3$ if $3|2n-1$ which can happen if $2n-1 \equiv 0 \pmod 3$ or $n\equiv 2 \pmod 3$. Or is equal to $1$ if $3\not \mid 2n-1$ which can happen if $n\equiv 0, 1 \pmod 3$.
And another way:
$\gcd(4n+4, 6n+3) = \gcd(4(n+1), 3(2n+1)=$.
... as $3(2n+1)$ is odd....
$\gcd(n+1, 3(2n+1))$.
Now $\gcd(n+1, 2n+1) = \gcd(n+1, (2n+1)-(n+1) = \gcd(n+1, n) = \gcd(n+1 - n, n) = \gcd(1, n) = 1$.
So... $\gcd(n+1, 3(2n+1)) = \gcd(n+1, 3)$.
Which is $3$ if $3|n+1$ and is $1$ if not.
Perhaps we can retrofit this as
$\gcd(3,n+1) = \{1,3\}$
$\gcd(2n+1, n+1) = 1$ so
$\gcd(3(2n+1), n+1) = \gcd(3,n+1)$.
$\gcd(3(2n+1), 2) = 1$ so
$\gcd(3(2n+1), 2^2(n+1)) = \gcd(3,n+1)$.
All comes down to "casting out" relatively prime factors.
$\begin{align} (\color{#c00}4(n\!+\!1),\,3(2n\!+\!1))\, &=\, (n\!+\!1,\,3(\color{#0a0}{2n\!+\!1}))\ \ \ {\rm by}\ \ \ (\color{#c00}4,3)=1=(\color{#c00}4,2n\!+\!1)\\[.2em] &=\, (n\!+\!1,3)\ \ {\rm by} \ \bmod n\!+\!1\!:\ n\equiv -1\,\Rightarrow\, \color{#0a0}{2n\!+\!1\equiv -1} \end{align}$
Remark $ $ Your argument that the gcd $\,d\mid \color{#c00}3$ is correct, but we can take it further as follows
$$d = (4n\!+\!4,6n\!+\!3) = (\underbrace{4n\!+\!4,6n\!+\!3}_{\large{\rm reduce}\ \bmod \color{#c00}3},\color{#c00}3) = (n\!+\!1,0,3)\qquad$$
Therefore $\, d = 3\,$ if $\,3\mid n\!+\!1,\,$ else $\,d= 1$
