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

1. ## 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??

2. 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.

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.

3. 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.