greatest common divisor of two elements

Question

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 ?

Answer 1

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). $$

Answer 2

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.

Answer 3

$\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$