# 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
$\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??
• Jul 10th 2010, 05:04 PM
undefined
Quote:

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.

Quote:

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.
• Jul 10th 2010, 05:14 PM
chiph588@
Quote:

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.