Prove that $n^2 + n +1$ is not divisible by $5$ for any $n$ 
Prove that $n^2 + n +1$ is not divisible by $5$ for any $n$.

I believe this might be tried using division algorithm, or modular arithmetic. I don't see exactly how to start this... Please help.
 A: If you don't know modular arithmetic you can also show it by induction. This is similar to the solution by rschwieb:


*

*Prove that if $n^2 + n + 1$ is not divisible by $5$, then also $(n+5)^2 + (n+5) + 1$ is not divisible by $5$.

*Prove explicitly the base cases: $n = 1, n=2, n=3, n=4, n=5$.

*By induction this then holds for all $n$.

A: it's enough to check it for $n\in\{0,1,2,3,4\}$:
\begin{array}{c}
  n^2+n+1
    & \equiv
    & \begin{Bmatrix}
      0 + 0 + 1\\
      1 + 1 + 1\\
      4 + 2 + 1\\
      4 + 3 + 1\\
      1 + 4 + 1
      \end{Bmatrix}
    & (\operatorname{mod}5)
  \\
    & \equiv
    & \begin{Bmatrix}
      1\\
      3\\
      2\\
      3\\
      1
      \end{Bmatrix}
    & (\operatorname{mod}5)
\end{array}
where each 'vector' entry corresponds to a choice of $n$ (i know it's sloppy but tex gives me a headache)
A: It is not true :$1^2+1+1=3$ but $5$ does not divide $3$ 
A: actually it is never divisible by 5. To prove it, consider the possible class where $n$ belongs to, mod 5
A: In fact $n^2+n+1$ is never divisible by $5$ for any $n$.
If it were, then the equation $n^2+n+1=0$ would hold mod 5, and you can verify by brute force it doesn't happen.
A: $5\nmid (n^2+n+1)$ for all integer $n$. Because
$$n^2+n+1 \equiv (n+3)^2 + 2 \pmod 5$$
So if $5\mid (n^2+n+1)$ for some $n$, then $n$ satisfies $(n+3)^2 \equiv 3 \pmod 5$. But $3$ is not quadratic residue modulo $5$. (You can check that $3$ is not quadratic residue easily.)
A: This solution is les elegant but seems more easier to come up with to me.
If $5|n^2+n-1 \rightarrow n^2+n=-1 \mod 5\rightarrow (n+1)(n)=1\mod 5$
So all you have to check is 5 tiny multiplications. (three if you don't do the one with zeroes.)
A: Suppose $5$ divides $n^2+n+1$.  Then $5$ also divides $(n-2)^2+2 = n^2+n+1-5(n-1)$. For every $n$, we know that $(n-2)^2$ must have its last digit equal to one of $1,4,5,6,9$ (this is true of the squares of all integers).  But then the last digit of $(n-2)^2 +2$ must be among $1,3,6,7,8$, a contradiction.
A: $\rm mod\ 5\!:\ 0\equiv (1\!-\!n)(1\!+\!n\!+\!n^2)\equiv \color{#C00}1\!-\!\color{#0A0}{n^3}\Rightarrow \color{#C00}n\equiv \color{#0A0}{n^4}\!\equiv 1\ or\,\ 0\:$ by Fermat. But $1,0$ are not roots.
