Prove that $k^2+k+1$ is not divisible by $101$ for any natural $k.$

Question

Prove that $k^2+k+1$ is not divisible by $101$ for any natural $k.$

Answer 1

Hint: If $101|k^{2}+k+1$, then $101|4(k^{2} + k + 1) = (2k+1)^{2} + 3$, which implies that $\left(\frac{-3}{101}\right) = 1$. However, you may show that $\left (\frac{-3}{101}\right) = -1$ by using the quadratic reciprocity.

Answer 2

Let $$k^2+k+1\equiv0(\mod101).$$ $k\equiv0(\mod101)$ is impossible, which says that we can assume that $k$ is not divisible by $101$.

Now, $$(k-1)(k^2+k+1)\equiv0(\mod101)$$ or $$k^3\equiv1(\mod101).$$ But by the Fermat's Little theorem $$k^{100}\equiv1(\mod101),$$ which gives $$k\equiv1(\mod101),$$ which gives $1^2+1+1$ is divisible by $101$, which is a contradiction.