# Given $a\equiv x\pmod p$ and $b\equiv y\pmod q$, can we deduce a congruence relating $a,b,c,y$ modulo $pq$?

Assume that \begin{align*} a &\equiv x \pmod p \\ b &\equiv y\pmod q.\end{align*}

Does this imply an equation involving the numbers $a,b,x,y$ modulo $pq$? One possible example would be $$ab \equiv xy\mod pq$$

-
Not quite. Take $a = 0$, $x = p$, $b = 1$, and $y = q+1$. Then your suggestion gives $$0 \equiv (q+1)p \bmod pq$$ which doesn't have to be true! However, if you avoid picking anything that reduces to 0..? (Also, I'm guessing $p$ and $q$ are primes?) – Alex Feb 23 '12 at 14:42
I don't think you can do better than $$ab\equiv (x\mod q)(y\mod p)\mod pq$$ since the value of $x\mod p$ and $y\mod q$ don't tell you much about $x\mod q$ and $y\mod p$. – Alex Becker Feb 23 '12 at 14:54
Well, you have $$(a-x)(b-y) \equiv 0 \mod pq$$ – Joel Cohen Feb 23 '12 at 15:04

Here is an equivalent question: given that $(a - x)$ is a multiple of $p$ and $(b - y)$ is a multiple of $q$, can we conclude that something is a multiple of $pq$? The answer is yes: $(a - x)(b - y)$, $(a - x)q$, and $p(b - y)$ all must be multiples of $pq$. So, among other things, we have:

\begin{align*}(a - x)(b - y) &\equiv 0\phantom{0} \pmod{pq}\\ aq &\equiv xq \pmod {pq}\\ pb &\equiv py \pmod{pq}.\end{align*}

The first equation might look nicer if we multiply it out:

$$ab + xy \equiv ay + xb \pmod{pq}.$$

-

There is similiar law $$a \equiv b\pmod n \\c \equiv d\pmod n$$ imply $$ac \equiv bd\pmod n \\a+c \equiv b+d\pmod n$$

-
{"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": 1, "mathjax_display_tex": 1, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "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.9951764345169067, "perplexity": 528.5257890230614}, "config": {"markdown_headings": true, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 10, "end_threshold": 15, "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-2016-30/segments/1469257824201.56/warc/CC-MAIN-20160723071024-00014-ip-10-185-27-174.ec2.internal.warc.gz"}