- #1

- 125

- 0

## Homework Statement

How many solutions does [tex]x^{2}\equiv9 mod 7700[/tex] have?

So my question is if this solution is "legitimate"

Solution

First notice that[tex] 7700=7\cdot11\cdot2^{2}\cdot5^{2}[/tex]

Thus we must solve the system [tex]\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}.

[/tex]

This system is equivelent to

[tex]\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}. [/tex]

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]

## Homework Equations

## The Attempt at a Solution

Last edited: