show that for any $n \in \mathbb{Z}$ gcd($n^2 - n + 1, n +1)$ is either $1$ or $3$.

Question

show that for any $n \in \mathbb{Z}$ gcd($n^2 - n + 1, n +1)$ is either $1$ or $3$.

My Work:

I considered the case where $n =-1$ , and the case $n \not= 1$.

So when $n\not= -1$ we can let $n^2 - n+ 1 = (n-2)(n + 1) + 3$.

We know that when $n=1$ it is clear that the gcd is $1$. However I am having trouble with the case when $n \not= 1$ any help on this would be great!

Answer 1

Hint $\ $ By Euclid's algorithm $\ \gcd(n\!+\!1,\,3+(n\!+\!1)k) = \gcd(n\!+\!1,3)$