2
$\begingroup$

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 ?

$\endgroup$
3
$\begingroup$

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

$\endgroup$
  • $\begingroup$ thanks for answering $\endgroup$ – Mustafa Azzurri Jan 2 at 17:50
0
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.