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

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!

• Are you familiar with Legendere symbol and quadratic reciprocity? – Anurag A Dec 10 '18 at 3:34
• Yes I am familiar with both but do not totally understand when and how to apply the concept – joseph Dec 10 '18 at 3:39
• Oh I think I see what you mean. So can I say that $5\equiv 1\pmod{4}$ so the legendre symbol of 5 on p equals the legendre symbol of p on 5. Then just replace p with its least positive residue mod 5? – joseph Dec 10 '18 at 3:42

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$$).
• @mjoseph you don't really need explicit $x$, only that $f'(x)=2x$ is nonzero (using $f(x)=x^2-5$). But that is obvious from $x^2\equiv 5\pmod{p}$) – user10354138 Dec 10 '18 at 4:05