## Homework Statement

How many solutions does $$x^{2}\equiv9 mod 7700$$ have?
So my question is if this solution is "legitimate"
Solution

First notice that$$7700=7\cdot11\cdot2^{2}\cdot5^{2}$$

Thus we must solve the system $$\begin{cases} x^{2}\equiv2 & \left(7\right)\\ x^{2}\equiv9 & \left(11\right)\\ x^{2}\equiv\mbox{1} & \left(4\right)\\ x^{2}\equiv9 & \left(25\right)\end{cases}.$$
This system is equivelent to
$$\begin{cases} x\equiv\pm2 & \left(7\right)\\ x\equiv\pm9 & \left(11\right)\\ x\equiv\pm1 & \left(4\right)\\ x\equiv\pm9 & \left(25\right)\end{cases}.$$
since gcd(1,p)=1 is always true, all of these equations are solvable by the fundamental theorem of modulo arithmetic. There are [tex]2^{4}=16[tex] disjoint equations and thus 16 distinct solutions.

Each solution must be distinct, since if x solves to different equations, then for instance we would have [tex]x\equiv2\equiv-2\left(7\right)[tex]

Last edited: