# Number of solutions of quadratic congruence

I'm studying quadratic congruences with composite moduli, something of the form:

$$x^2\equiv a\pmod n$$

where $\gcd(a;n)=1$, but something I can't manage to find is how many solutions does one of them actually have without, well, solving it directly. I know that if $n=p$ a prime the congruence has either $0$ or $2$ incongruent solutions but what can we say about the general case ? Is there a general formula or at least some applicable in specific cases (different from the one that I mentioned).

edite note: actually I know how to solve this kind of equation decomposing the modulus and using the Chinese reminder theorem so I'm only interested in determining the number of solutions without actually compute them.

• Maybe you can start by decomposing $n=p_1^{b_1}...p_n^{b_n}$. Interesting question. – Maman Sep 27 '16 at 22:42

If $n$ is small enough, you could probably list all the residues of $n$ squared, modulo $n$, and see which of these is equal to $a$. In the general case, you will likely need to use the prime factorization $n = p_1^{a_1} \dots p_r^{a_r}$, and then use the Chinese Remainder Theorem along with a way of solving $x^2 \equiv a \pmod{p_i^{a_i}}$ for all $1 \leq i \leq r$.
To solve $x^2 \equiv a \pmod{p^k}$, this article goes through the procedure in detail, so I won't repeat it here.
As for how many solutions the congruence has, by the Chinese Remainder Theorem, it would be the product over the number of solutions each of $x^2 \equiv a \pmod{p_i^{a_i}}$ has.