2
$\begingroup$

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 \begin{equation} c \equiv (b - a) \cdot m^{-1} \;(\!\!\!\!\!\!\mod n) \end{equation} and am asked to prove $x = a + cn$ (I believe should be $x = a + cm$) is a solution to \begin{equation} x \equiv a \;(\!\!\!\!\!\!\mod m) \qquad x \equiv b \;(\!\!\!\!\!\!\mod n), \end{equation} 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 \begin{equation} x \equiv b \;(\!\!\!\!\!\!\mod n) \implies k \equiv (b - a) \cdot m^{-1} \;(\!\!\!\!\!\!\mod n). \end{equation} (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 \begin{equation} x = a + m(b - a) \cdot m^{-1} + mn\ell \end{equation} 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.

$\endgroup$
  • 1
    $\begingroup$ You're right about it being $x=a+cm$ rather than $x=a+cn$. $\endgroup$ – anon Jul 12 '13 at 4:46
  • $\begingroup$ 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.] $\endgroup$ – Peter Smith Jul 12 '13 at 8:54
  • 1
    $\begingroup$ 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. $\endgroup$ – Alex Jul 12 '13 at 14:12
1
$\begingroup$

Let me offer you reassurance "that these are in fact typos in the question."

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

$\endgroup$

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.