I want to know how many classes of modulo $143$ are squares. This is equivalent to find how many $a$ can make $$\begin{align*} x^2 \equiv a \pmod{143} && (1) \end{align*}$$ has solutions
On the other hand, I know that $143=11 \times 13$ and $(11,13)=1$, so $$\begin{align*} x_0 \text{ is a solution of (1) } \iff x_0 \text{ is a solution of} \begin{cases} x^2 \equiv a \pmod{11} \\ &&(2) \\ x^2 \equiv a \pmod{13} \end{cases} \end{align*}$$ That is $a$ is a square modulo $143 \iff a$ is a square modulo $11$ and is a square modulo $13$
It's not hard for me to find that $$1^2=1, \ 2^2=4,\ 3^2=9,\ 4^2=5,\ 5^2=3 \pmod{11}$$ are squares modulo $11$ and $$1^2=1,\ 2^2=4,\ 3^2=9,\ 4^2=3,\ 5^2=12,\ 6^2=10 \pmod{13}$$ are squares modulo $13$ . Based on this information, I'm a little confused to compute how many squares there exist modulo $143$
I think at least, $a=1,4,9$ are squares $\pmod{143}$ , since this time in $(2)$ , plug in $a=1,4,9$ we can pick $x=1,2,3$ , these numbers satisfiy $(2)$ , so $x=1,2,3$ should also satisfy $x^2 \equiv 1,4,9 \pmod{143}$
Also, I find that if $a$ modulo $11$ is $5$ and modulo $13$ is $3$, then $x=4$ is a solution of $(2)$; By some computation, I find the number satisfies this is $16$; similarly, if $a$ modulo $11$ is $3$ and modulo $13$ is $12$, then $x=5$ is a solution of $(2)$. I find the number satisfies this is $25$.
They are $1,4,9,16,25$ all squares modulo $143$. If they are, is the number of squares of modulo $143$ just equal to the number of squares of modulo $11$ (that is, the smaller number in $11 \times13$)
Any help on this? Thanks.
So there should be $6\cdot 7=42.$ These can be gotten under the isomorphism between $$\Bbb Z_{11}×\Bbb Z_{13}$$ and $$\Bbb Z_{143}.$$ For instance, using Bezout, we can map $(x,y)$ to $-7×11×y+6×13×x.$
You can now check that for instance, $(3,12)\mapsto -924+234\equiv-690\equiv-118\equiv25.$ And $(4,0)\mapsto312\equiv26.$
Etc.
It's well-known that modulo a prime $p$, there are $(p+1)/2$ quadratic residues.
This follows from Euler's criterion: $$\left(\frac ap\right)\equiv a^{\frac {p-1}2}\pmod p,$$ since there are $(p-1)/2$ solutions to $x^{\frac{p-1}2}\equiv1$. Plus zero is always a quadratic residue.