1
$\begingroup$

Consider two different prime numbers $x$ and $y$. Show that the following is true: For every pair of numbers $m$ and $n$ so that $0\le m<x$ and $0\le n< y$, there is a unique integer $q$, where $0\le q<xy$, so that:$$q\equiv m \mod x\\ q\equiv n \mod y$$

To start this problem, I'm thinking that we have to find the number of $q$'s in the range $[0,xy)$ that can have the same result modulo $x$ and modulo $y$ and count how many $q$'s there are.

$\endgroup$
1
  • 1
    $\begingroup$ Do you already know the Chinese Remainder Theorem? $\endgroup$ Feb 18 '14 at 3:20
1
$\begingroup$

Since $x$ and $y$ are prime numbers, use Euclid's Algorithm to find $r$ and $s$ such that $rx + sy = \gcd(x,y)=1$. Take $q\equiv (nrx+msy) \mod xy$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.