2
$\begingroup$

I'm trying to find the number of solutions to this congruence: $$x^2\equiv 121\pmod {1800}$$

I thought about writing it as a system of congruences. As $1800=3^2 \cdot 5^2 \cdot 2^3$, we get:

$x^2\equiv 121\pmod {5^2} \;,\; x^2\equiv 121\pmod {3^2} \;,\; x^2\equiv 121\pmod {2^3}$

$\Downarrow$

$ x^2\equiv 21\pmod {5^2} \;,\; x^2\equiv 4\pmod {3^2} \;,\; x^2\equiv 1\pmod {2^3} $

Now I'm pretty stuck with how to solve each of the above quadratic congruences, is there a fast way to do it?

Thanks

$\endgroup$
2
$\begingroup$

Hint:

We need $\left(\dfrac x{11}\right)^2\equiv1\pmod{3^2,5^2,2^3}$

Now we can prove $y^2\equiv1\pmod{p^n}$ has exactly two solutions for prime $p\ge3$ and integer $n\ge1$

Finally we can apply Chinese Remainder Theorem to find the number of in-congruent solutions to be $$4\cdot2^2$$

See also: Number of solutions of $x^2=1$ in $\mathbb{Z}/n\mathbb{Z}$

$\endgroup$
5
  • 1
    $\begingroup$ But for example the congruence $x^2\equiv 1\pmod {2^3}$ has 4 solutions: $1,3,5,7$ $\endgroup$
    – user401516
    Jun 4 '18 at 9:35
  • $\begingroup$ @user401516, Thanks, please follow the link in my post $\endgroup$ Jun 4 '18 at 9:40
  • $\begingroup$ Thanks, but I still don't understand why what you stated is correct. Also, how can I find the number of solutions when $p=2$? $\endgroup$
    – user401516
    Jun 4 '18 at 9:52
  • $\begingroup$ @user401516, Have you followed the link $\endgroup$ Jun 4 '18 at 9:54
  • $\begingroup$ I haven't learned the theorem used there, also I'm pretty sure there is a simpler solution. $\endgroup$
    – user401516
    Jun 4 '18 at 10:14
1
$\begingroup$

No, there's not a fast way. To solve $x^2\equiv a \pmod{p^n}$ we first solve $x^2\equiv a \pmod{p}$ and then use Hensel's Lemma to "lift" the solution to $\pmod{p^2}$ and then $\pmod{p^3}$, etc. Sometimes the solutions lift uniquely, sometimes not.

In the case of your problem, there are two solutions modulo $5$ which lift uniquely to two solutions modulo $25$. The exact same thing happens modulo $9$. There is one solution modulo $2.$ It lifts to two solutions modulo $4.$ Each of these in turn lifts to two solutions modulo $8$, for a total of 4 solutions modulo $8.$

So in the end, there are $2\times 2\times 4 = 16$ solutions modulo $1800.$

$\endgroup$
1
  • 1
    $\begingroup$ I should add that a "fast" square root algorithm for non-prime moduli would be an earth-shattering invention. Half of all cryptosystems would be compromised. $\endgroup$
    – B. Goddard
    Jun 4 '18 at 16:20

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.