[Math] Solve $x^2+x+7 \equiv 0\pmod{81}$

elementary-number-theorymodular arithmeticnumber theory

Solve $x^2+x+7\equiv 0 \pmod{81}$


My work:

Prime factorization $81 = 9^2 = 3^4$

Test the value $x\equiv0,1,2$ for $x^2+x+7\equiv0\mod{3}$

we have $x\equiv1\mod{3}$ works.

Now life this to $\mod{3^2} = \mod{9}$

Let $x=1+3k$ for some integer$k$

$(1+3k)^2 + (1+3k) +7 \equiv0\mod{9}$

$1+6k+0+1+3k+7\equiv0\mod{9}$

$9+9k\equiv0\mod9$

$1+k\equiv0\mod9$

$k\equiv-1\mod9$

$k=-1+9m$ for some integer m

Lift again to $\mod81$

$(-1+9m)^2 + (-1+9m)+7\equiv0\mod81$

$-9m+7\equiv0\mod81$

I cant continue… how can I make it work???

thanks!!

Best Answer

You can write the equation as $(x +41)^{2} \equiv -27$ (mod 81). But this means there is no solution, as $x+41$ would need to be divisible by $9.$ I'll put in more explanation, in view of comments and questions, including correcting a sign error pointed out in the comments. We have $x^{2} + x + 7 \equiv x^{2}+ 82x + 7 $ (mod 81). This is (mod 81), equal to $(x+41)^{2}+ 7 -1600,$ and also $1600 \equiv -20$ (mod 81). Hence we need $(x+41)^{2} \equiv -27$ (mod 81), which is impossible in integers.