# x≡a (mod m) and x≡a(mod n) implies x≡a (mod mn)

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 :)

• Well, $amn(m' + n') \equiv 0 \mod mn$ so you must have done something wrong. – fleablood Apr 20 '18 at 16:03
• "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$. – fleablood Apr 20 '18 at 16:04
• You want $n*n' \equiv 1 \mod m$ and $m*m' \equiv 1 \mod n$. – fleablood Apr 20 '18 at 16:21
• ugh thx for reminding me, it's my first time to type in this form so it's a little bit messy... – Cluyeia Apr 20 '18 at 16:30

## 3 Answers

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

• thx man, it's really helpful i will keep it in mind :-] – Cluyeia Apr 20 '18 at 16:51
• nice extended discussion of the rabbit-hole that the OP was going down... pretty much trying to prove something the hard way. – Joffan Apr 20 '18 at 17:11
• 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$. – fleablood Apr 20 '18 at 23:31
• @fleablood I do the same, pairwise can give you good control. – 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)$

• 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. – Cluyeia Apr 20 '18 at 16:34
• @Cluyeia They are relatively prime so have no common factors. Thus if they both divide a number, so does their product. – Joffan Apr 20 '18 at 16:40
• yeah u're right, maybe i've wrote something wrong during the exam then lmao. thx anyway ;D – Cluyeia Apr 20 '18 at 16:53
• 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. – 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$.