# Number of modular square root of an integer mod a square-free number.

The question came from H.Iwaniec's "Topics in Classical Automorphic Forms" Lemma 4.8

Let $$q$$ be an odd square-free number, and let $$(\frac{c}{d})$$ be the extended Jacobi symbol:

1. If $$c,d>0$$, then $$(\frac{c}{d})$$ is the usual Jacobi symbol,
2. For $$c\neq 0$$, $$(\frac{c}{d})=\frac{c}{|c|}(\frac{c}{-d})$$,
3. $$(\frac{0}{d})=\begin{cases}1,\, d=\pm 1\\ 0, \,\text{otherwise} \end{cases}$$

The text claims that $$\#\{x\bmod{q}:x^2\equiv y\pmod{q}=\prod_{-p|q}\Big(1+\big(\frac{y}{p}\big) \Big)$$

Could someone please give more details about why this equal sign holds true? Thanks a lot.

• In point 2, do you mean $c\neq0$ and $d<0$? Apr 16 at 16:22
• Also asked here but it is not clear if the single answer has been checked by anyone. Apr 16 at 16:24
• @Arthur Yes, when $d<0$, one can transfer to $d>0$ by the formula.
– scd
Apr 16 at 16:25

By the Chinese Remainder Theorem, if $$p_1,\ldots,p_r$$ are pairwise distinct primes, then for each choice of integers $$a_1,\ldots,a_r$$ there exists an $$a$$ (unique modulo $$q=p_1\cdots p_r$$) such that \begin{align*} a&\equiv a_1\pmod{p_1}\\ a&\equiv a_2\pmod{p_2}\\ &\vdots\\ a&\equiv a_r\pmod{p_r}. \end{align*}

Say you are trying to solve $$x^2\equiv b\pmod{q}$$. Using the Chinese Remainder Theorem, that is equivalent to solving the system of congruences \begin{align*} x^2&\equiv b\pmod{p_1}\\ x^2&\equiv b\pmod{p_2}\\ &\vdots\\ x^2&\equiv b\pmod{p_r} \end{align*} because if you find solutions $$a_1,\ldots,a_r$$ to these $$r$$ congruences, then you can look for an $$a$$ that satisfies the system of congruences in my first display, and this $$a$$ will necessarily solve $$x^2\equiv b\pmod{q}$$.

Moreover, every tuple $$(a_1,\ldots,a_r)$$ of solutions to these $$r$$ congruences will give you a new solution to $$x^2\equiv b\pmod{q}$$, and different tuples correspond to different solutions.

So to count the solutions to $$x^2\equiv b\pmod{q}$$ modulo $$q$$, we can count the number of tuples of solutions to the system of $$r$$ congruences, instead.

If $$\gcd(b,q)=1$$, then $$x^2\equiv b\pmod{p_i}$$ will have either $$0$$ or $$2$$ solutions (because $$p_i$$ is odd and $$b\not\equiv 0\pmod{p_i}$$). But this is exactly $$1 + \left(\frac{b}{p_i}\right)$$ where $$\left(\frac{b}{p_i}\right)$$ is the Legendre symbol: because you get $$0$$ is the symbol is $$-1$$ (there are no solutions), and $$2$$ if the symbol is $$1$$ (yes, there are solutions).

If $$\gcd(b,q)\neq 1$$, then there will be some primes $$p_i$$ for which $$p_i|b$$; in those cases, you have the congruence $$x^2\equiv 0\pmod{p_i}$$, which has exactly one solution. But again, this is $$1+\left(\frac{b}{p_i}\right)$$! Because $$\left(\frac{b}{p_i}\right)$$ is $$0$$, and you have a total of one solution.

So, how many tuples $$(a_1,\ldots,a_r)$$ are there? There are the number of possible $$a_1$$, times the number of possible $$a_2$$, etc. And this is precisely $$\prod_{i=1}^r\Bigl(\#\text{ solutions to }x^2\equiv b\pmod{p_i}\Bigr) = \prod_{i=1}^r\left( 1+ \left(\frac{b}{p_i}\right)\right).$$

So the number of solutions to $$x^2\equiv b\pmod{q}$$ modulo $$q$$ is then exactly the value of this product.