Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question
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$.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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