I want to find how many solutions the congruence $x^2 \equiv 121 \mod 1800$ has.

What is the method to find it without calculating all the solutions? I can't use euler criterion here because 1800 is not a primitive root. thanks!!!


As $(121,1800)=1,$ $$x^2\equiv121\pmod{1800}\iff(x\cdot 11^{-1})^2\equiv1$$

Now as $1800=3^2\cdot2^3\cdot5^2$

as $y^2\equiv1\pmod{p^n}$ has exactly two in-congruent solutions for odd prime $p$

and $y^2\equiv1\pmod8$ has four

the number of solutions $$(x\cdot 11^{-1})^2\equiv1\pmod{1800}$$ will be $2\cdot4\cdot2$

| cite | improve this answer | |
  • $\begingroup$ hi, thank you but I didn't understand 2 things: 1. how did you get that: $ x^2\equiv121\pmod{1800}\iff(x\cdot 11^{-1})^2\equiv1 $ and 2. why do you multiply to get the number of solutions? $\endgroup$ – CnR May 1 '16 at 9:19
  • $\begingroup$ @CnR, See johndcook.com/blog/quadratic_congruences $\endgroup$ – lab bhattacharjee May 1 '16 at 9:35
  • $\begingroup$ it doesn't explain my questions :( $\endgroup$ – CnR May 1 '16 at 9:53
  • $\begingroup$ @CnR, See math.stackexchange.com/questions/345668/… $\endgroup$ – lab bhattacharjee May 1 '16 at 9:55
  • $\begingroup$ I really don't understand how what I asked and these links are related.. I appreciate your help but would like more elaborated explanation so I can undersand the steps of your proof $\endgroup$ – CnR May 1 '16 at 14:17

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.