# Find G. C. F. of $(8n^3 + 8n, 2n+1)$

I'm stuck with this problem, I divided $$8n^3 + 8n$$ by $$2n+1$$ and obtained $$5$$, so now my G. C. F is $$\gcd(2n+1, -5)$$.

What's next? I can't divide $$2n+1$$ by $$-5$$.

• so that means that it isn't divisible and therefore gcd is 1. Wolframalpha confirms this. wolframalpha.com/input/?i=gcd%288n%5E3%2B8n%2C+2n%2B1%29 – user29418 Nov 12 at 20:11
• If $n=2$, then $2n+1$ is divisible by $5$. – egreg Nov 12 at 20:23
• Sure you can. If $n =2$ or $n = 7$ or $n=12$ or .... But did it occur to you that maybe you are doe. Is $\gcd(8n^3 + 8n, 2n+1) = \gcd(2n+1, 5)$ and acceptable answer? Why or why not? If not, would would an acceptable answer look like. Can we go further. – fleablood Nov 12 at 21:26

$$8n^3+8n=4n(2n^2+2)$$ $$=4n[n(2n+1)-n+2]$$ $$=4n^2(2n+1)+4n(2-n)$$ $$=4n^2(2n+1)-2n(2n+1)+10n$$ $$=(2n+1)[4n^2-2n+5]-5$$ the residu is $$-5$$.

$$2n+1$$ is irreductible and $$8n^3+8n$$ is not a multiple of $$2n+1$$, thus they are coprime. the gcd is $$1$$.

• What if $n=2$ ? – lhf Nov 12 at 20:55
• @lhf I think the OP deals with polynomials. – hamam_Abdallah Nov 12 at 21:29

Judging from the notation, it's quite likely that the exercise is not asking about polynomials, but about integers.

It's perfectly good to perform the polynomial division, because it holds for any value of $$n$$.

Since you found that the remainder is $$-5$$, you can conclude that the greatest common divisor of the two integers $$8n^3+8n$$ and $$2n+1$$ is a divisor of $$5$$, hence either $$1$$ or $$5$$.

It is $$5$$ if and only if $$2n+1$$ is divisible by $$5$$, that is, $$2n\equiv4\pmod{5}$$, which simplifies to $$n\equiv2\pmod{5}$$. Thus you have $$\gcd(8n^3+8n,2n+1)= \begin{cases} 5 & n\equiv2\pmod{5} \\[4px] 1 & n\not\equiv2\pmod{5}\end{cases}$$

Well, you figured out that $$\gcd(8n^3 +8n, 2n+1) = \gcd(2n+1, -5)$$.

And as $$\gcd(\pm a, \pm b) = \gcd(a b)$$ we know $$\gcd(8n^3 + 8n, 2n+1) = \gcd(2n+1,5)$$.

As $$5$$ is prime then $$\gcd(2n+1, 5)$$ is either $$1$$ or $$5$$.

It is $$5$$ if $$5|2n+1$$. ANd it is $$1$$ if $$5\not\mid 2n+1$$.

And $$5|2n+1 \iff$$

$$2n+1 \equiv 0 \pmod 5 \iff$$

$$2n \equiv -1 \pmod 5 \iff$$

$$n \equiv 2 \pmod 5$$.

$$\gcd(8n^3+8n, 2n+1) =\begin{cases} 5 &\text{if } n\equiv 2 \pmod 5\\1&\text{if } n\not\equiv 2 \pmod 5\end{cases}$$
Since $$8n^3+8n=(2n+1)[4n^2-2n+5]-5$$, we have that $$\gcd(8n^3+8n,2n+1)$$ divides $$5$$ and so is either $$1$$ or $$5$$. Both cases do occur:
For $$n=1$$, we get $$\gcd(8n^3+8n,2n+1)=1$$.
For $$n=2$$, we get $$\gcd(8n^3+8n,2n+1)=5$$.
In fact, $$\gcd(8n^3+8n,2n+1)=5$$ iff $$n \equiv 2 \bmod 5$$; otherwise $$\gcd(8n^3+8n,2n+1)=1$$.