$x^2\equiv 5 \pmod{1331p^3}$

Question

Let $p$ be given by $p=2^{89}-1$ and note that it is a Mersenne Prime. The problem is to find the number of incongruent solutions to $$ x^2\equiv 5 \pmod{1331p^3} $$ I began the problem by splitting it up into the congruences $$ x^2\equiv 5 \pmod{1331} $$and$$ x^2\equiv 5 \pmod{p^3} $$ I found that $x\equiv 4,7\pmod{11}$ are solutions to $x^2\equiv 5\pmod{11}$ and then use Hansel's Lemma all the way up to get that $x\equiv 1258, 73\pmod{1331}$ are solutions to the equation $\pmod{1331}$.
I think all I have to do is solve the second equation and use the Chinese Remainder Theorem at the end but I am stuck because I have no idea where to begin in solving $x^2\equiv 5\pmod{p}$ as p is such a large number.
Any help is appreciated!

Answer 1

Consider Legendere symbol $\left(\frac{5}{p}\right)$. By quadratic reciprocity $$\left(\frac{5}{p}\right)\Big(\frac{p}{5}\Big)=(-1)^{\left(\frac{5-1}{2}\right)\left(\frac{p-1}{2}\right)}=1 \implies \left(\frac{5}{p}\right)=\left(\frac{p}{5}\right).$$ But $p=2^{89}-1 \equiv 2(2^2)^{44}-1 \equiv 1 \pmod{5}$. Thus $$\left(\frac{5}{p}\right)=\left(\frac{p}{5}\right)=\left(\frac{1}{5}\right)=1.$$ Thus $5$ is indeed a QR modulo $p$. Since $p$ is a prime thus $x^2 \equiv 5 \pmod{5}$ will have two non-congruent solutions. Now you can apply Hensel to see if you will continue to have two solutions as you lift from $p$ to $p^3$.

If you have two solutions for $p^3$ as well, then in all you will have $4$ solutions (combining with two from the previous congruence with $11^3$).