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!!

  • $\begingroup$ 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. $\endgroup$ Oct 24 '13 at 13:48
  • $\begingroup$ 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". $\endgroup$ Oct 24 '13 at 13:51
  • $\begingroup$ woops. Sorry for the typos. $\endgroup$ Oct 24 '13 at 19:15
  • $\begingroup$ Your first sentence was still unreadable, so I rewrote it into what I think you meant. But please correct of I misinterpreted. $\endgroup$ 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.


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.