Assume $m\ \mathrm{and}\ n\ \mathrm{are\ two\ relative\ prime\ positive\ integers.}$

Given $x \equiv a\ \pmod m$ and $x \equiv a\ \pmod n$.

Prove that $x \equiv a\ \pmod {mn}\ \mathrm{by\ using\ Chinese\ Remainder\ Theorem}.$

And I did the following:
$$ \mathrm {M_1 = }\ n\ \ and\ \ \mathrm {M_2 = }\ m\ \\ \mathrm {y_1 = }\ n’\ \ and\ \ \mathrm {y_2 = }\ m’ \\ \mathrm{where}\ n\cdot n’\equiv 1\ \mathrm{(mod}\ m) \ \ and\ \ m\cdot m’\equiv1\ \mathrm{(mod}\ n) \\ Then\ x\equiv\ (a\cdot n\cdot n’\ +a\cdot m\cdot m’ )\pmod{mn} $$
But how could I conclude “$x \equiv a\ (\mathrm {mod}\ mn)$” from the last statement or I did it wrongly? I would be grateful for your help :)

  • $\begingroup$ Well, $amn(m' + n') \equiv 0 \mod mn$ so you must have done something wrong. $\endgroup$ – fleablood Apr 20 '18 at 16:03
  • $\begingroup$ "where n⋅n′≡1 (mod n) and m⋅m′≡1 (mod n)" Isn't obvious that no such $n'$ or $m'$ exist? $n*n' \equiv 0 \mod n$ for all $n'$ and $m*m'\equiv 0 \mod m$. $\endgroup$ – fleablood Apr 20 '18 at 16:04
  • $\begingroup$ You want $n*n' \equiv 1 \mod m$ and $m*m' \equiv 1 \mod n$. $\endgroup$ – fleablood Apr 20 '18 at 16:21
  • $\begingroup$ ugh thx for reminding me, it's my first time to type in this form so it's a little bit messy... $\endgroup$ – Cluyeia Apr 20 '18 at 16:30

Well every number is equivalent to itself mod any modulus.

So $a\equiv a \mod mn$ and $a \equiv a \mod m$ and $a \equiv a \mod n$. So $x = a \mod mn$ is one solution.

But the Chinese remainder theorem claims that the solution is unique $\mod mn$.

So $x \equiv a \mod mn$ is the solution.


What you were trying to do was

$M = mn$

and $n'*n \equiv 1 \mod m$ and $m'*m \equiv 1 \mod n$

So $x \equiv an'n + am'n \equiv a(n'n + m'm) \mod mn$.

Which shunts the question to what is $(n'n + m'm) \mod mn$.

$n'n + m'm \equiv 1 \mod n$ and $n'n + m'm \equiv 1 \mod m$ so $(n'n + m'm) = 1 + kn = 1 + jm$ (for some integers $j,k$) so $kn = jm $ but $n$ and $m$ are relatively prime. So $n|j$ and $k|m$ and $kn = jm = lnm$ (for some integer $l$) and $(n'n + m'm) = 1 + lmn \equiv 1 \mod mn$.

  • $\begingroup$ thx man, it's really helpful i will keep it in mind :-] $\endgroup$ – Cluyeia Apr 20 '18 at 16:51
  • $\begingroup$ nice extended discussion of the rabbit-hole that the OP was going down... pretty much trying to prove something the hard way. $\endgroup$ – Joffan Apr 20 '18 at 17:11
  • $\begingroup$ The thing is I never could remember or set my variables up to do the whole $x = a_1m_1'\frac M{m_1} + ....$ wherem $m_i\frac M{m_i}\equiv m_i$. I just prefer to solve it pair by pair and figur $x \equiv a_1 + kn \equiv a_2 +jm \mod mn$ and use euclids algorithm to solve $jm -kn \equiv a_2 - a_1$. If $a_2 = a_1$ then we get the trivial $jm -kn = 0$. $\endgroup$ – fleablood Apr 20 '18 at 23:31
  • $\begingroup$ @fleablood I do the same, pairwise can give you good control. $\endgroup$ – Joffan Apr 20 '18 at 23:48

We have:
$n \mid (x-a)$, and
$m \mid (x-a)$

and $n$ and $m$ have no common factors, so
$nm \mid (x-a)$

  • $\begingroup$ Actually I answered this in my midterm exam and I got marks deducted, the professor said $nm | (x-a)$ is always true when both n and m are primes but in this case, they are just relatively prime. $\endgroup$ – Cluyeia Apr 20 '18 at 16:34
  • $\begingroup$ @Cluyeia They are relatively prime so have no common factors. Thus if they both divide a number, so does their product. $\endgroup$ – Joffan Apr 20 '18 at 16:40
  • $\begingroup$ yeah u're right, maybe i've wrote something wrong during the exam then lmao. thx anyway ;D $\endgroup$ – Cluyeia Apr 20 '18 at 16:53
  • $\begingroup$ Admittedly your specification is "using the Chinese remainder theorem" so maybe omitting that would get a mark knocked off. fleablood's answer is better that way, although exactly how CRT applies is glossed over a little bit. $\endgroup$ – Joffan Apr 20 '18 at 17:10

$x\equiv a\bmod n$ implies there exists a $k\in\Bbb Z$ such that $x=nk+a$. Now, we have $$nk+a\equiv a\bmod m\Rightarrow nk\equiv0\bmod m\Rightarrow k\equiv0\bmod m,$$ so then there exists a $j\in\Bbb Z$ such that $k=jm$. Substituting this in our equation for $x$ gives $$x=njm+a,$$ which means that $x\equiv a\bmod nm$.


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.