How to find $\gcd(n+1, n^2+7)$?

Question

I've tried to use the rule that if $ b>a$, then $\gcd(a,b)=\gcd(b,b−a)$, as well as the properties of divisibility by adding and subtracting the terms from each other but haven't been able to reach a conclusion.

Answer 1

Suppose $d = \gcd (n+1,n^2+7)$. Then $d|n+1$ and $d|n^2+7$. $$n^2+7 = n^2 + n - n + 7 = n(n+1) - (n-7)$$ So, $$d|n^2+7 \implies d|n(n+1) - (n-7) \implies d| n-7$$ since $d|n+1$ and hence $d|n(n+1)$. Now, $$d|n-7 \text{ and } d|n+1 \implies d|n+1 - n + 7 \implies d|8$$ and we have $d|8$. Got it?

Answer 2

Another approach: We can alway construct number n in terms of prime p such the $n+1$ and $n^{2k}+p$ have a common divisor like $d=p+1$, we may write:

$n=m(p+1)-1\rightarrow n+1=m(p+1)$

$n^{2k}+p= M[p(m+1)]+1+p= t(p+1)$

where $M[p(m+1)]$ means a multiple of $p(m+1)$. In your question $p=7$, so any number of the form $n=8m-1$ gives $n+1=8m$ and $(8m-1)^2+7=8t$ such that common divisor becomes $p+1=7+1=8$. Hence $n+1$ and $n^2+p$ for particular values of n can have common divisor.

Answer 3

$$\gcd(n+1,n^2+7)=\gcd(n+1,-n+7)=\gcd(n+1,8)$$ If $n=8k+r,$ this equals $\gcd(r+1,8).$

• I used that $\gcd(a,b)=\gcd(a,b+ka).$