<s>[INST] 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!
 [/INST] 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.
</s>