# Math Help - 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.
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 0, "mathjax_display_tex": 0, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 13, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0, "katex": 0, "math-container": 0, "wp-katex-eq": 0, "align": 0, "equation": 0, "x-ck12": 0, "texerror": 0, "math_score": 0.9538885354995728, "perplexity": 557.7639685114616}, "config": {"markdown_headings": true, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 10, "end_threshold": 5, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "plain"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "warc_path": "s3://commoncrawl/crawl-data/CC-MAIN-2015-40/segments/1443736676622.16/warc/CC-MAIN-20151001215756-00242-ip-10-137-6-227.ec2.internal.warc.gz"}