# Complete System of Residues modulo $m=m_1m_2…m_r$

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

• 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? – Jason Ng Oct 2 '18 at 13:57
• And also why we have to assume that congruence equation to show no repetition? – Jason Ng Oct 2 '18 at 14:35