# Find how many solutions the congruence $x^2 \equiv 121 \mod 1800$ has

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$

• 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? – CnR May 1 '16 at 9:19
• – lab bhattacharjee May 1 '16 at 9:35
• it doesn't explain my questions :( – CnR May 1 '16 at 9:53
• – lab bhattacharjee May 1 '16 at 9:55
• 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 – CnR May 1 '16 at 14:17