# 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 '19 at 20:11
• If $n=2$, then $2n+1$ is divisible by $5$. – egreg Nov 12 '19 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 '19 at 21:26

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