# Problem related to Chinese Remainder Theorem

I'm not sure if there is a typo in the question or if I am incorrect (will point out as I get to it), but I am given that $a,b,m,n$ are integers with $\gcd(m,n) = 1$ and that $$c \equiv (b - a) \cdot m^{-1} \;(\!\!\!\!\!\!\mod n)$$ and am asked to prove $x = a + cn$ (I believe should be $x = a + cm$) is a solution to $$x \equiv a \;(\!\!\!\!\!\!\mod m) \qquad x \equiv b \;(\!\!\!\!\!\!\mod n),$$ and that every solution to the system of congruences has the form $x = a + cn + ymn$ (I believe should be $x = a + cm + ymn$) for some $y \in \mathbb{Z}$.

I start by stating that as $\gcd(m,n) = 1$, the Chinese Remainder Theorem states that there is in fact a unique solution to the congruence up to congruence in $\mathbb{Z}/_{mn\mathbb{Z}}$. As $x \equiv a \;(\!\!\!\!\mod m)$, we have that $x = a + mk$ for $k$ an integer and since $\gcd(m,n) = 1$, $m$ has an inverse, $m^{-1}$ in $\mathbb{Z}/_{n\mathbb{Z}}$. Hence $$x \equiv b \;(\!\!\!\!\!\!\mod n) \implies k \equiv (b - a) \cdot m^{-1} \;(\!\!\!\!\!\!\mod n).$$ (Note: we are given this as an assumption, where $c = k$, so I'm not sure why this assumption would be provided.) This then provides $k = (b - a) \cdot m^{-1} + n\ell$ for $\ell$ and integer, and so $$x = a + m(b - a) \cdot m^{-1} + mn\ell$$ is the general solution to the congruence, with $a + m(b - a) \cdot m^{-1}$ being the unique solution in $\mathbb{Z}/_{mn\mathbb{Z}}$. (Note that $m^{-1} \cdot m \neq 1$ as this is not modulo $n$.)

With $\ell = y$ and $(b - a) \cdot m^{-1} = c$ this solution would make complete sense if I was asked to show that $x = a + cm$ and $x = a + cm + ymn$ are the solutions instead of $x = a + cn$ and $x = a + cn + ymn$. Could someone please show me where I may have made a mistake or missed something, or reassure me that these are in fact typos in the question.

• You're right about it being $x=a+cm$ rather than $x=a+cn$. – anon Jul 12 '13 at 4:46
• You don't say where the question is posed. If it is a local example sheet, alert your instructor. If it is a textbook question email the author. [Speaking from experience, you kick yourself when told about typos, but it is a lot more annoying not to be told.] – Peter Smith Jul 12 '13 at 8:54
• The question is from a Springer published textbook. I didn't see any errata for the book, but I will email the authors later today; thank you for suggesting this to me. – Alex Jul 12 '13 at 14:12

You are correct that it ought to be $\,x = a + c\,\bf m\,$ and not $\,x = a+ c\,\bf n,\,$ and also about $\,x = a + c\,{\bf m} + ymn$ and not $\,x = a + c\,{\bf n} + ymn$.