# 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

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

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

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

$\displaystyle \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
$\displaystyle x^2\equiv 1 \ \mbox{(mod p) and} x^2\equiv 1 \ \mbox{(mod q)}$, where p and q are distinct primes, it follows $\displaystyle x^2\equiv 1 \ \mbox{(mod pq)?}$
This is true.

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

Originally Posted by dwsmith
$\displaystyle (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
$\displaystyle x^2\equiv 1 \ \mbox{(mod p) and} x^2\equiv 1 \ \mbox{(mod q)}$, where p and q are distinct primes, it follows $\displaystyle 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.