2
$\begingroup$

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

  • 9
    Homework? It looks like it...2010-10-10
  • 0
    I have certainly set similar problems as homework in the past :-)2010-10-10

2 Answers 2

2

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.

0

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?

  • 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).2010-10-11
  • 0
    + for the first sentence, @Jonas Kibelbek.2011-04-02