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!

  • $\begingroup$ Are you familiar with Legendere symbol and quadratic reciprocity? $\endgroup$ – Anurag A Dec 10 '18 at 3:34
  • $\begingroup$ Yes I am familiar with both but do not totally understand when and how to apply the concept $\endgroup$ – joseph Dec 10 '18 at 3:39
  • $\begingroup$ 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? $\endgroup$ – 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$).

  • $\begingroup$ The OP isn't having trouble with that part, as demonstrated by his mod 11^3 calcuatlions. He is asking for help with finding the square-root of 5 mod p, not about lifting that square-root from mod p to mod p^3. $\endgroup$ – user10354138 Dec 10 '18 at 3:55
  • $\begingroup$ @user10354138 From the language of the question, OP wants to find the number of solutions (not the actual solutions). So if we can know the number of solutions for both congruences then you can have the number of solutions for the given congruence. My answer is in that regards. $\endgroup$ – Anurag A Dec 10 '18 at 3:57
  • $\begingroup$ I had this but I didn't think it was helpful as I can't use Hensel's Lemma unless I know explicit values of f(x) and f '(x). $\endgroup$ – joseph Dec 10 '18 at 4:03
  • 1
    $\begingroup$ @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}$) $\endgroup$ – user10354138 Dec 10 '18 at 4:05
  • $\begingroup$ Oh yes that is obvious. Thank you so much! $\endgroup$ – joseph Dec 10 '18 at 4:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.