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

Question

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

Answer 1

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

Answer 2

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

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

Answer 3

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