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.

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


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.