# x^2\equiv 1 (mod p) and x^2\equiv 1 (mod q), where p and q are distinct primes

• Jul 10th 2010, 04:49 PM
dwsmith
x^2\equiv 1 (mod p) and x^2\equiv 1 (mod q), where p and q are distinct primes
$x^2\equiv 1 \ \mbox{(mod p) and} x^2\equiv 1 \ \mbox{(mod q)}$, where p and q are distinct primes, it follows $x^2\equiv 1 \ \mbox{(mod pq)?}$

$p|(x^2-1) \ \mbox{and} \ q|(x^2-1)$

$pq|(x^2-1)^2\rightarrow (x^2-1)^2\equiv 0 \ \mbox{(mod pq)}$

$\rightarrow (x^2-1)^2\equiv 0 \ \mbox{(mod pq)}\rightarrow 1^2\equiv 0 \ \mbox{(mod pq)}\rightarrow 1\not\equiv 0 \ \mbox{(mod pq)}$.

Since this isn't true, then no??
• Jul 10th 2010, 05:04 PM
undefined
Quote:

Originally Posted by dwsmith
$x^2\equiv 1 \ \mbox{(mod p) and} x^2\equiv 1 \ \mbox{(mod q)}$, where p and q are distinct primes, it follows $x^2\equiv 1 \ \mbox{(mod pq)?}$

This is true.

In general $a \equiv b\ (\text{mod}\ m)$ and $a \equiv b\ (\text{mod}\ n)$ implies $a \equiv b\ (\text{mod}\ \text{lcm}(m,n))$. See this MathWorld page, property #11.

Quote:

Originally Posted by dwsmith
$(x^2-1)^2\equiv 0 \ \mbox{(mod pq)}\rightarrow 1^2\equiv 0 \ \mbox{(mod pq)}$

I don't see how you made this step.
• Jul 10th 2010, 05:14 PM
chiph588@
Quote:

Originally Posted by dwsmith
$x^2\equiv 1 \ \mbox{(mod p) and} x^2\equiv 1 \ \mbox{(mod q)}$, where p and q are distinct primes, it follows $x^2\equiv 1 \ \mbox{(mod pq)?}$

This is correct and you have the right idea on how to prove it.

See here for full a proof.