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

Printable View

July 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??
July 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.
July 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.

All times are GMT -8. The time now is 10:37 PM.

Copyright © 2005-2013 Math Help Forum. All rights reserved.

Copyright © 2005-2013 Math Help Forum. All rights reserved.