without actually finding then, determine the number of solutions of the congruence. $$x ^2 \equiv 3 \pmod {11^2 . 23^2}$$
My professor gave a hint of finding the order of the group of units and the solution at the back of the book is 4, but I do not know how to use the hint and how the solution is as it is? could anyone help me in understanding this?
On
Let $S(f,n)$ denote the set of solutions of congruence equation $f(x)\equiv 0 \pmod{n}$ for $f=\sum_{i=0}^{m}{a_ix^i}\in\mathbb{Z}[x]$. Denote $N(f,n)=|S(f,n)|$.
Lemma 1: Let $n=\prod_{i=1}^{k}{p_i^{e_i}}$ where $p_i$ are distinct primes and $e_i$ are positive integers. Then $N(f,n)=\prod_{i=1}^{k}{N(f,p_i^{e_i})}$.
Lemma 2: Define $f'(x)=\sum_{i=1}^{m}{ia_ix^{i-1}}$. If $S(f,p)\cap S(f',p)=\emptyset$, then $N(f,p^l)=N(f,p)$, where $p$ is a prime and $l$ is an positive integer.
Lemma 3: $N(x^k-n,p)=\gcd(k,p-1)$ if $N(x^k-n,p)>0$ and $p\not\mid n$.
1) Put $f(x)=x^2-3$, $n=11^2\cdot 23^2$ and We have $$N(x^2-3,11^2\cdot 23^2)=N(x^2-3,11^2)\cdot N(x^2-3, 23^2)=N(x^2-3,11)\cdot N(x^2-3, 23),$$ since $S((x^2-3)',p_i)=\{0\}$ and $0\notin S(x^2-3,p_i)$.
2) To determinate $N(x^2-3, 11)$ and $N(x^2-3, 23)$, we need some results about the Legendre symbol for prime $p$, $$\left({\frac {a}{p}}\right)={\begin{cases}1&{\text{if $x^2\equiv a\pmod{e}$ has solutions}},\\-1&{\text{if $x^2\equiv a\pmod{e}$ has no solutions}},\\0&{\text{if }}a\equiv 0{\pmod {p}}.\end{cases}}$$ In fact it is easy to calculate Legendre symbol if $p\not\mid n$. That is $$\left({\frac {a}{p}}\right)\equiv a^{\frac{p-1}{2}}\pmod{p}.$$
Using Legendre symbol, we have $\left({\frac {3}{11}}\right)\equiv 3^{\frac{11-1}{2}}\equiv 1\pmod{11}$ and $\left({\frac {3}{23}}\right)\equiv 3^{\frac{23-1}{2}}\equiv 3\cdot 9\cdot 6\equiv 1 \pmod{23}$. Note that $$3^2\equiv 9 \pmod{23},$$ $$3^4\equiv (3^2)^2 \equiv 81 \equiv 12\pmod{23},$$ $$3^8\equiv (3^4)^2 \equiv 144 \equiv 6\pmod{23},$$ Due to Lemma 3, $N(x^2-3, 11)=N(x^2-3, 23)=2$.
3) To sum up, $N(x^2-3,11^2\cdot 23^2)=2\cdot 2=4$, i.e., the congruence equation $x^2\equiv 3 \pmod{11^2\cdot 23^2}$ has 4 solutions.
Here is another solution which follows the direction of your professor. You can recall some thing in your another post here. We use the same notations in that post.
1) Let $n=11^2\cdot 23^2$. It is not hard to obtain $$\mathbb{Z}_{n}^*\cong \mathbb{Z}_{11^2}^*\times \mathbb{Z}_{23^2}^*\cong (C_{11} \times C_{10}) \times (C_{23} \times C_{22})=(C_{55} \times C_{2}) \times (C_{253} \times C_{2}).$$
Therefore $x^2\equiv 1 \pmod{n}$ has $|1\times C_2\times 1 \times C_2|=4$ solutions. Or we can say $y^2\equiv 1 \pmod{n}$ has 4 solutions, where $x,y$ are unknowns.
2) In this part, we assert that $3$ is a quadratic residue modulo $11^2$ and $23^2$, respectively. Assume that you know how to calculate the order of $3$ modulo $11^2$ and $23^2$, respectively. The result is $$3^{5}\equiv 1 \pmod{11^2},3^{253}\equiv 1 \pmod{23^2}.$$ Thus $$3^{6}\equiv 3 \pmod{11^2},3^{254}\equiv 3 \pmod{23^2}.$$ Hence, one of the square root of $3$ modulo $11^2$ and $23^2$, is $3^3$ and $3^{127}$, respectively. Or if you do not what to find the square roots, then note that $a$ is a quadratic residue modulo $n$ if $\mathrm{Ord}(a)$ is odd. Hence $3$ is also a quadratic residue modulo $n$. Denote $y_0$ for one of the square root of of $3$ modulo $n$.
3) Now $x^2\equiv 3\equiv y_i^2\pmod{n}$. It is equivalent to $$\left(\frac{x}{y_0}\right)^2\equiv 1 \pmod{n}.$$ Let $y=\frac{x}{y_0}$. From Part 1), $y$ has 4 solution, and so is $x$. So your answer is 4.
The key is to convert the equation $x^2\equiv a\pmod{n}$ into other equation $y^2\equiv 1\pmod{n}$.