# Proof using Chinese Remainder Theorem for $n=p_1^{m_1}\cdot p_2^{m_2}\cdots p_k^{m_k}$

I wish to find an expression for the number of solutions $x$ to $x^2\equiv 9 \pmod n$, with $x$ a natural number${}<n$, when $n$ has a factorization $n=p_1^{m_1}\cdot p_2^{m_2}\cdots p_k^{m_k}$ into distinct prime powers.

I have already found that for the different cases of $p_i$, that for $2^k$, $k \ge 3$ there are always 4, similarly for $3^k, k \ge 3$ there are 6. For $p^k$ there are 2.

I have experimented and it follows that for a composite $n$, I simply multiply the distinct prime powers together to get the number of solutions, but I am struggling with trying to express this formally.

I know that the CRT states that there exists a $k$, $1 \le k \le n-1$, s.t.

$$k \equiv b \pmod {p_1}$$ $$k \equiv c \pmod {p_2}$$ .... $$k \equiv z \pmod {p_3}$$

for each distinct prime factor of $n$. But how can I bind all these different residues back to $9$? Because the CRT does not state this.

Any help would be greatly appreciated!!

-
You can start by adding/permuting the words in the part of the initial sentence after "that", so that the can be parsed. The subject seems to be "number of solutions", but I cannot locate the verb that goes with it. –  Marc van Leeuwen Oct 24 '13 at 13:48
And there seem to be some $p$'s missing in your formula in the title; exponents and subscripts appear to be attached to a "floating point". –  Marc van Leeuwen Oct 24 '13 at 13:51
woops. Sorry for the typos. –  JackReacher Oct 24 '13 at 19:15
Your first sentence was still unreadable, so I rewrote it into what I think you meant. But please correct of I misinterpreted. –  Marc van Leeuwen Oct 25 '13 at 4:12

CRT is what you want to use: Just notice that if there are $a_i$ solutions for $p_i^{m_i}$, then there are $a_1 \dots a_k$ different tuples $(x_1,\dots,x_k)$ where $x_i$ is a solution for $p_i^{m_i}$. Now for any such tuple there exists a unique $x$ in $\mathbb{Z}/n\mathbb{Z}$ such that $x \equiv x_i \pmod{p_i^{m_i}}$ for all $i$. In particular then $x_i^2 \equiv 9 \pmod{p_i^{m_i}}$ for all $i$, so $x^2 \equiv 9 \pmod{n}$. Conversely if $x^2 \equiv 9 \pmod{n}$, then $x^2 \equiv 9 \pmod{p_i^{m_i}}$ for all $i$, and it follows that $x$ corresponds to one of the $a_1 \dots a_k$ tuples.