Find the roots of $f(x)=x^2+x+1$ modulo 7, and modulo 13, and modulo 91

Question

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$?

Answer 1

To find the solutions to $x^2 + x +1 \mod k$ we can factor $x^2 + x + 1$ and to factor that we need to find the $nm \equiv 1 \mod k$ so that $n + m \equiv 1 \mod k$.

For $k = 7$, 7 is prime so every term has a multiplicative inverse. $1^{-1} = 1$ and $1 +1 \equiv 2$ so that won't do. $2^{-1}=4$ but $2+4 \equiv 6\equiv -1$. So

$x^2 + x+1 \equiv (x-2)(x-4) \mod 9$

And the solutions to that are $x =2, 4$

Likewise in $modulo 13$ $2^{-1} = 7$ but $2+7 \equiv 9$. $3^{-1} = 9$ and $3+9 \equiv -1$ so

$x^2 + x + 1 \equiv (x-3)(x-9) \mod 9$

And the solutions to that are $x=3, x=9$.

So we just need to use the chinese remainder theorem to solve the following four equations modulo $91 = 7*13$

$x \equiv 2 \mod 7; x \equiv 3 \mod 13$

$x \equiv 2 \mod 7; x \equiv 9 \mod 13$

$x \equiv 4 \mod 7; x \equiv 3 \mod 13$

$x \equiv 4 \mod 7; x \equiv 9 \mod 13$

$1 = 2*7 - 13$

So $-13*2 + 3*14 = 16$ is solution $2\mod 7; 3\mod 13$

$-13*2 + 9*14 \equiv 9 \mod 91$ is solution to $2\mod 7; 9 \mod 13$

$-13*4 + 3*14 \equiv 81 \mod 91$ is solution to $4\mod 7; 3 \mod 13$

$-13*4 + 9 *14 \equiv 74 \mod 91$ is solution to $4 \mod7; 3\mod 13$

=======

$x^2 + x +1 \mod 7\equiv$

$x^2 -6x + 8\mod 7 \equiv$

$(x-4)(x-2)\mod 7 \equiv$

$7$ is prime so there are not zero divisors.

So $4,2$ are the solutions modulo 7.

$x^2 + x + 1 \mod 13 \equiv$

$x^2 -12x + 27 \mod 13 \equiv$

$(x-3)(x-9)\mod 13$

So $3$ and $9$ are the solutions mod 13.

$91 =13*7$ solutions are

$4 + 7k \equiv 3 + 13j \mod 91$

Or $4 + 7k \equiv 9 + 13j \mod 91$

or $2 + 7k \equiv 3 + 13j \mod 91$

or $2 + 7k \equiv 9 + 13j \mod 91$

$4 + 7k \equiv 3 + 13j \mod 91$ is solved by $81=4 + 7*11 = 3+ 6*13$ and, indeed, $81^2 + 81 + 1 \equiv (-10)^2 -10 + 1 =91 \equiv 0 \mod 91$.

$4+7k \equiv 9 + 13j \mod 91$ is solved by $74 = 4+7*10 = 9 + 5*13$ and, indeed, $74^2 + 74 + 1 \equiv (-17)^2 - 17 + 1\equiv 16*17 + 1 \equiv 8*17*2 + 1 \equiv 136*2 + 1 \equiv 45*2 + 1 \equiv 91 \equiv 0 \mod 91$.

$2+7k \equiv 3 + 13j \mod 91$ is solved by $16=2 + 14 = 3 + 13$ and, indeed $16^2 + 16 +1= 17*16 + 1 $ ... didn't we just do this?

So $2+7k\equiv 9 + 13j$ is solved by $9 = 7+2 = 9$ and $9^2 + 9 + 1 = 91 \equiv 0 \mod 91$

Answer 2

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$.