Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
    
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

1 Answer 1

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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