[Math] 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$.