Is $x^2+x+1$ divisible by $101$, if $x\in\mathbb Z$? Prove $x^2+x+1$ isn't divisible by $101$, for any $x\in\mathbb Z$?
I think the way of solving the problem it by using "Fermat's Little Theorem".
 A: Oh, well. If $$ x^2 + x + 1 \equiv 0 \pmod {101}, $$ then multiplying by $4$ gives
$$ (2x+1)^2 + 3  \equiv 0 \pmod {101},  $$ and
$$ (2x+1)^2   \equiv -3 \pmod {101}.  $$
However, Legendre
$$ (-3|101) = (-1|101)  (3|101) =  (3|101) = (101|3) = -1 $$
NOTE: for any odd prime $p,$ we always get $(-3|p) = (p|3),$ all that matters is that $3 \equiv 3 \pmod 4.$ IF $p \equiv 1 \pmod 4,$
$$ (-3|p) = (-1|p)  (3|p) =  (3|p) = (p|3)$$
IF $q \equiv 3 \pmod 4,$
$$ (-3|q) = (-1|q)  (3|q) = - (3|q) = (q|3)$$
SIMILAR PROBLEM FOR ILLUSTRATION:  If $p$ is an odd prime and $$ x^2 + x + 2 \equiv 0 \pmod {p}, $$ then multiplying by $4$ gives
$$ (2x+1)^2 + 7  \equiv 0 \pmod {p},  $$ and
$$ (2x+1)^2   \equiv -7 \pmod {p}.  $$
However, Legendre
$$ (-7|p) = (p|7). $$
So, if $(p|7) = -1,$ it is impossible to have $ x^2 + x + 2$ divisible by $p.$ These primes, with $(p|7) = -1,$ are
$$  p \equiv 3,5,6 \pmod 7$$ and $101 = 98 +3$ is one of them.
ANOTHER SIMILAR PROBLEM FOR ILLUSTRATION:  If $p$ is an odd prime and $$ x^2 + x + 3 \equiv 0 \pmod {p}, $$ then multiplying by $4$ gives
$$ (2x+1)^2 + 11  \equiv 0 \pmod {p},  $$ and
$$ (2x+1)^2   \equiv -11 \pmod {p}.  $$
However, Legendre
$$ (-11|p) = (p|11). $$
So, if $(p|11) = -1,$ it is impossible to have $ x^2 + x + 3$ divisible by $p.$ These primes, with $(p|11) = -1,$ are
$$  p \equiv 2,6,7,8,10 \pmod {11}$$ and $101 = 99 +2$ is one of them.
A: Suppose that the congruence $x^2+x+1\equiv 0\pmod{101}$ has a solution. Then the congruence $x^3-1\equiv 0\pmod{101}$ has a solution $a$ not congruent to $1$. Thus $a$ has order $3$ modulo $101$. This is impossible, since $3$ does not divide $101-1$.
