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.

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

2 Answers 2

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|improve this answer
2  
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

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|improve this answer

Your Answer

 
discard

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