Find the roots of $f(x)=x^2+x+1$ modulo 7, and modulo 13, and modulo 91 Find the roots of $f(x)=x^2+x+1$ modulo $7$, and modulo $13$, and modulo $91$  
I think for mod $7$ and $13$, it can be done by trial and error. But how about mod $91$?
 A: For any odd modulus, 
$$x^2+x+1\equiv0\iff4x^2+4x+4\equiv0\iff(2x+1)^2\equiv-3$$
For the prime modulus $7$,
$$(2x+1)^2\equiv-3\equiv4\implies2x+1\equiv\pm2\implies4(2x+1)\equiv\pm8\implies x+4\equiv\pm1$$
which implies $x\equiv2$ or $x\equiv4$ mod $7$.
For the prime modulus $13$,
$$(2x+1)^2\equiv-3\equiv36\implies2x+1\equiv\pm6\implies7(2x+1)\equiv\pm42\equiv\pm3\implies x+7\equiv\pm3$$
which implies $x\equiv3$ or $x\equiv9$ mod $13$.
As for $91=7\cdot13$, The Chinese Remainder Theorem tells us there are four solutions to $x^2+x+1\equiv0$ mod $91$, and provides a procedure for finding them.  However, for this problem we're in luck:  It's easy to see that $x=9$ satisfies $x\equiv2$ mod $7$ and $x\equiv9$ mod $13$, while $x=16$ satisfies $x\equiv2$ mod $7$ and $x\equiv3$ mod $13$, so that $x=9$ and $16$ are two solutions.  This implies the other two solutions correspond to 
$$2x+1\equiv-(2\cdot9+1)\equiv-19\quad\text{and}\quad2x+1\equiv-(2\cdot16+1)\equiv-33$$
or $2x\equiv-20$ and $2x\equiv-34$, i.e., $x\equiv-10\equiv81$ and $x\equiv-17\equiv74$ mod $91$.  So the four solutions mod $91$ are $x=9$, $16$, $74$, and $81$.
