Show that the gcd of $(n^2, n^2 + n + 1) = 1$

Question

We know $(a,\;b)$ = $(a-kb,\;b)$, with $(x,\;y)$ meaning the greatest common divisor of x and y.

$(n^2,\;n^2 + n + 1)$ = $(n^2,\;(n+1)^2 - n)$

Let $d\;|\;n^2$ and let $d\;|\;((n+1)^2 -\;n)$ Then $d\;|\;n+1$, since by linear combination theorem $d\;|\;n^2$ and $d\;|\;(n^2+n+1)$ implies by subtraction that $d\;|\;(n+1)$

Also, since $d\;|\;n^2$, then $d\;|\;n$

Since $d\;|\;n$ then again by linear combination theorem $d\;|\;(n+1)^2$ $d\;|\;(n+1)^2$ implies $d\;|\;(n+1)$ $d\;|\;n$ and $d\;|\;(n+1)$ implies $(d,n) = 1$

Is this proof correct? Seems legit to me. This is my first proof typed out in MathJAX directly, and it started as my asking where to go from the "Also, since ..." but then I managed to complete it!

Answer 1

No, it is not correct, e.g. $\,d\mid n^2\,\Rightarrow\,d\mid n\,$ is true only for squarefree $\,d.$ Instead, note that $\,n^2+n+1 = n(n+1)+1\,$ is coprime to $\,n,$ so also coprime to $\,n^2,\,$ by Euclid's Lemma.

Or: $\ (n^2,n(n^2)-1) = (n^2,-1)=1,\,$ so $\,n^2\,$ is coprime to all factors of $\,n^3-1,\,$ viz. $\,n^2+n+1.$

Answer 2

Use the Euclidean Algorithm for Greatest Common Divisor:

$$n^2 + n + 1 = n^2 + (n+1)$$ $$n^2 = (n-1)(n+1) + 1$$

Hence the greatest common divisor is $1$.

Another way is to assume $d \mid n^2$ and $d \mid n^2 + n + 1$, where $d$ is prime number. Now $d$ divides their difference so we have:

$$d \mid n^2 + n + 1 - n^2 \implies d \mid n+1$$

Now since $d \mid n^2 \implies d \mid n$, we get that $d$ divides consecutive numbers, which is possible only for $d = 1$. Hence the proof.