Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

First question: Let $a$, $b$, $c$ be distinct primes larger than $3$, and let $x = abc$. Show that if $p$ is a positive integer and $p^2 \equiv 9 \pmod {x}$, then $p \equiv \pm 3 \pmod {a}$, $p \equiv \pm 3 \pmod{b}$, and $p \equiv \pm 3 \pmod{c}$.

Second question: Using the fact that $1001 = (7)(11)(13)$ find the eight solutions to $y^2 \equiv 9 \pmod{1001}$ in the set $\{ 1, 2, 3,\ldots, 1000 \}$.

share|cite|improve this question
Homework? It looks like it... – J. M. Oct 10 '10 at 5:41
I have certainly set similar problems as homework in the past :-) – Robin Chapman Oct 10 '10 at 8:10

HINT$\rm\ \ a|x|(p-3)(p+3)\ \Rightarrow \ a\:|\:p-3\ \: or\ \: a\:|\:p+3\:,\:$ since $\rm\:a\:$ is prime. Combine this with the Chinese remainder theorem to solve the second question. See also my answer here.

share|cite|improve this answer

okay ive figured out the first part, now ive been told the chinese remainder theorem for the second part but i dont see how it will give me the extra 2 answers since it only allows the set 1-1000 I assume the first 6 answers are x ≡ +-3(mod y) where y=7,11,13 yet what about the other 2 answers?

share|cite|improve this answer
You're not counting the solutions correctly. Think about your proof-- You should have shown that every solution to p^2≡9(mod 1001) must satisfy p≡3(mod 7) or p≡-3(mod 7). So this condition does not just apply to the first two answers; it applies to all 8. You actually have four answers ≡3(mod 7) and four answers ≡-3(mod 7). – Jonas Kibelbek Oct 11 '10 at 2:15
+ for the first sentence, @Jonas Kibelbek. – awllower Apr 2 '11 at 7:33

Your Answer


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