# greatest common divisor of two elements

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

• thanks for answering – Mustafa Azzurri Jan 2 at 17:50

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