# Two little number theory questions

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 \}$.

-
Homework? It looks like it... –  Guess who it is. 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

## 2 Answers

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.

-

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?

-
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