Q: Suppose that $m_1,m_2,...,m_r$ are pairwise relatively prime positive integers. For each $j$, let $f(m_j)$ denote a complete system of residues modulo $m_j$.Show the the numbers $$c_1+c_2m_1+...+c_rm_1m_2...m_{r-1}$$ form a complete system of residues modulo $m=m_1m_2...m_j$, where $c_j \in f(m_j)$.

My Thought: I nearly have no idea to do this question. Someone show me an answer of this question. He firstly assume $$c_1+c_2m_1m_2+...+c_rm_1m_2...m_{r-1} \equiv d_1+d_2m_1m_2+...+d_rm_1m_2...m_{r-1} \quad \text{mod } m$$ $$(c_1-d_1)+(c_2-d_2)m_1m_2+...+(c_r-d_r)m_1m_2...m_{r-1} \equiv 0 \quad \text{mod } m$$ Then saying $m_1|c_1-d_1$ so that $c_1=d_1$. Further to continue, divides the congruence equation by $m_1$. (I understand this step as $m$ are relatively prime, dividing $m_1$ is a possible operation). Then continue the above procedures with $c_2$ until $c_r$.

can anyone help me to explain more in detail what it is going on? Or what is the target in the questions. Thank You.


You added an extra $m_2$ at the second term, which should be $c_2m_1$ (note that the $i$th term does not contain $m_i$).

We write $a\equiv b\pmod{n}$ to mean that $a$ and $b$ give the same remainder modulo $n$, i.e. $n\,|\,a-b$.

The proof you wrote then proves that there is no repetition among the values modulo $m$.
Indeed, if $\ c_1+c_2m_1+c_3m_1m_2+\dots+c_rm_1m_2\dots m_{r-1}\ \equiv\ d_1+d_2m_1+\dots+d_rm_1m_2\dots m_{r-1} \pmod m$,
then $m\,|\ (c_1-d_1)+\,(\dots)m_1$, hence indeed $m_1|\,c_1-d_1$, i.e. $c_1\equiv d_1\pmod{m_1}$ which now implies $c_1=d_1$ as they from a system of residues.
Going forward, we have $m\,|\ (c_1-d_1)+(c_2-d_2)m_1+\,(...)m_1m_2\ =(c_2-d_2)m_1+\,(...)m_1m_2$, so in particular $$m_2\,|\ (c_2-d_2)m_1$$ which implies $m_2\,|\ (c_2-d_2)$ because $\gcd(m_1,m_2)=1$.
And, so on. In the end, we will arrive to $c_i=d_i$ for all $i$.

Finally, either one can count the numbers arising with the different $c_i$'s, or we can directly show that every residue modulo $m$ is represented:
Let $a\in\Bbb Z$ be any integer, we can explicitly find the $c_i$ 'coordinates' for it:
There's a unique $c_1\in f(m_1)$ such that $a\equiv c_1\pmod{m_1}$.
Now, as $m_1$ is coprime to $m_2$, there is a unique $c_2$ such that $c_2m_1\equiv(c_1-a)\pmod{m_2}$.
And so on..

  • $\begingroup$ It makes me clear about the steps. By the way, I want to further ask why "showing the residue are all distinct" can implies it is the complete residue system? $\endgroup$ – Jason Ng Oct 2 '18 at 13:57
  • $\begingroup$ And also why we have to assume that congruence equation to show no repetition? $\endgroup$ – Jason Ng Oct 2 '18 at 14:35

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.