4
$\begingroup$

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$

  • 4
    Well, you have $(a-x)(b-y) \equiv 0 \mod pq$2012-02-23

2 Answers 2

3

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}.$

1

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 $