# finding a unique integer using mod

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.

-
Do you already know the Chinese Remainder Theorem? –  Bill Dubuque Feb 18 '14 at 3:20

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