Number of solutions to $x^2\equiv a\pmod m$

Solution 1:

After a few attempts I arrived at this stage but it seems to me that there is something missing here. Can anybody point my mistakes or guide me into the right direction?

Solution : \textbf{Lemma 1} Let $a$ be an integer and $b$ a positive integer, and let $b=p_1^{\alpha_1}p_2^{\alpha_2}\cdots p_r^{\alpha_r}$ be the factorization of $b$ into primes. Then $a$ is a quadratic residue modulo $b$ if and only if $a$ is a quadratic residue modulo $p_i^{\alpha_i}\;;\forall i=1,2,\ldots,r$.\vspace{2mm}

Proof. If $a$ quadratic residue modulo $b$, it is clearly so modulo each $p_i^{\alpha_i}$, for each $i=1,2,\ldots,r.$ Which intern shows $a$ is quadratic modulo each $p_i$.\vspace{1mm}

Conversely, Assume that $a$ is a quadratic residue modulo each $p_i^{\alpha_i}$ and $x_i$ is an integer such that $x_i^2\equiv a\pmod p_i^{\alpha_i}$. According to (CRT) there is an $x$ such that $x\equiv x_i\pmod p_i^{\alpha_i};\,\forall i$. Then $x^2\equiv x_i^2\equiv a \pmod p_i^{\alpha_i}$ for each $i$ and therefore $x^2\equiv a \pmod b$.\vspace{2mm}

\textbf{Lemma 2} Let $p$ be an odd prime and $a$ be an integer. Prove that, if $a$ is a quadratic residue $\pmod p$, then it is a quadratic residue $\pmod p^k$ for all positive integers $k$.\vspace{2mm}

Proof. A simple induction suffices. Suppose that $x^2\equiv a\pmod{p^k}$ with integer $x$ and $k$; that is, $x^2=a+tp^k$ where $t$ is also an integer. Then for any integer $n$, we have $(x+np^k)^2\equiv a+(t+2nx)p^k\pmod{p^{k+1}}$. Choosing $n$ to satisfy the linear congruence $t+2nx\equiv 0\pmod p$, we get $(x+np^k)^2\equiv a\pmod{p^{k+1}}$.\vspace{1mm}

The existence of $n$ satisfying the linear congruence $t+2nx\equiv 0\pmod{p}$ follows from $(2x)n\equiv (-t)\pmod{p}$ is a linear Diophantine equation and $\gcd{(2x,p)}\mid (-t)$.\vspace{2mm}

\textbf{Definition 1} Given a prime number and an integer $a$, the Legendre's symbol is defined as $$\left(\frac ap\right)=\left\{\begin{array}{cl}1,&\mbox{if } p\nmid a\mbox{ and } a \mbox{ is a quadratic residue (mod }p);\\ -1, &\mbox{if }p\nmid a \mbox{ and }a \mbox{ is a quadratic nonresidue (mod } p);\\ 0,&\mbox{if }p\mid a.\end{array}\right.$$\vspace{1mm}

\textbf{Definition 2} Let $a$ be an integer and $b$ an odd number and let $b=p_1^{\alpha_1}p_2^{\alpha_2}\cdots p_r^{\alpha_r}$. Then Jacobi's symbol is defined as $$\left(\frac ab\right)=\left(\frac a{p_1}\right)^{\alpha_1} \left(\frac a{p_2}\right)^{\alpha_2}\cdots\left(\frac a{p_r}\right)^{\alpha_r}$$.\vspace{2mm}

\textbf{Lemma 3} Given a prime $p$ and an integer $a$, the equation $x^2\equiv a \pmod p$ has either zero, one or exactly two solutions.\vspace{2mm}

Proof. Suppose that the considered congruence has a solution $x_1\neq 0$. Then so clearly $-x_1$ is a solution. As $x_1^2=(-x_1)^2$. Then there are no other solutions modulo $p$ as $x^2\equiv a\equiv x_1^2\pmod p\implies x\equiv \pm x_1\pmod p$. Now note that If the above congruence has no solution means $a$ is a quadratic non-residue of $p$ thus $\left(\frac{a}{p}\right)=-1$ or $\left(\frac{a}{p}\right)+1=0$ next if the congruence has exactly one solution then $a\equiv 0\pmod p\implies \left(\frac{a}{p}\right)=0\implies 1+\left(\frac{a}{p}\right)=1$ and finally if the congruence has exactly two solutions then $a$ is a quadratic residue of $p$ and thus $\left(\frac{a}{p}\right)=1\implies 1+\left(\frac{a}{p}\right)=2$. Thus we see in each case the quantity $1+\left(\frac{a}{p}\right)$ represents the number of solutions of the equation $x^2\equiv a \pmod p$. Thus we can restate lemma 3 as the equation $x^2\equiv a \pmod p$ has exactly $$1+\left(\frac{a}{p}\right)$$ number of solutions.\vspace{2mm}

Note from Definition 2, It is easy to see that $\left(\frac ab\right)=-1$ implies that $a$ is a quadratic nonresidue modulo $b$. Indeed, if $\left(\frac ab\right)=-1$ then by definition $\left(\frac a p_i\right)=-1$ for at least one $p_i|b$. Hence $a$ is a quadratic non-residue modulo $p_i$. Now Lemma 1 and Lemma 2 and Definition 2 together clearly shows that\vspace{1mm}

1. $a$ is a quadratic residue modulo $b$ an odd, \textit{iff} $a$ is a quadratic residue modulo $p$ such that $p|b$.\
2. If $a$ is a quadratic non-residue modulo $b$ an Odd, squarefree integer then $\left(\frac a p_i\right)=-1$ for at least one $p_i|b$.\
3. If $p|a$ then $\gcd(a,b)\neq 1$.

Therefore in our given question $m$ is taken to be odd square free integer, thus again by (CRT) we see that the number of solutions to the equation $x^2\equiv a\pmod m$ is infact $$\prod\limits_{p|m}\left(1+\left(\frac a p\right)\right)$$. Clearly \textbf{1} gives the maximum when $\prod\limits_{p|m}\left(1+\left(\frac a p\right)\right)=\prod\limits_{p|m}2=2^r$ where $r$ is the number of prime divisors of $m$. \textbf{2} gives the minimum when for atleast one prime $p_i$ we have $\left(\frac a p_i\right)=-1\implies \prod\limits_{p|m}\left(1+\left(\frac a p\right)\right)=0$.