Show that the gcd of $(n^2, n^2 + n + 1) = 1$ 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!

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