Multiplication of Moduli in Modular Congruences Lately it's come up in my discrete mathematics class that proving things for smaller congruences, namely those where the modulus is a prime is much easier than attempting to do so for larger congruences. 
For example, one such problem was to prove that $a^5 \equiv a \pmod{10}$ for $a$ $\varepsilon$ $\mathbb Z^+\ $This problem on its own becomes difficult only because we are not guaranteed that for every a $(a,10)=1$. The solution was to factorize 10 in terms of primes $p_1, p_2... p_n$ s.t for each prime $p_i$ $(a,p_i)=1$ for all $a \ \varepsilon \ \mathbb Z^+\ $, resulting in n congruences under modulo the given prime and then apply Euler's Theorem. In this case we find the following:
$$10 = 2 \cdot 5$$
so
$$a^{\phi(5)} \equiv 1 \pmod{5} \\ a^{\phi(2)} \equiv 1 \pmod{2}$$
since $\phi(5)=4, \phi(2)=1$ this becomes:
$$a^{4} \equiv 1 \pmod{5} \implies a^{5} \equiv a \pmod{5}\\ a^{1} \equiv 1 \pmod{2} \implies a^{5} \equiv a^4 \pmod{2} $$
but since a is its own inverse modulo 2, we can transform the 2nd congruence into:
 $$a^5 \equiv a \mod{2}$$
Then the part that I am unclear on occurs. It seems that we can just multiply the 2 moduli together and the desired congruence falls out that:
$$a^5 \equiv a \pmod{10}$$
So my question is whether or not $a \equiv b \pmod{n}$ and $a \equiv b \pmod{m}$ always$\implies$ $a \equiv b \pmod{mn}$.
Edit (Extension):
The answer to my question has been stated to be yes provided that $(m,n) = 1$ but I also noticed that if my 2 relations had been left stated as 
$$a^4 \equiv 1 \pmod{2}$$
$$a^4 \equiv 1 \pmod{5}$$
Applying the conjecture I made gives:
$$a^4 \equiv 1 \pmod{10}$$
which is demonstrably false given that $$2^4 \equiv 6 \pmod{10} \implies 2^4 \not\equiv 1 \pmod{10}$$
Why is this and what prevents this identity from being true as well? I see that 2 would then not be coprime to 10 but why does it work when I multiply both sides by a then?
 A: Excellent question!
The short answer is no.
For example, $4 \equiv 16 \pmod 6$ and $4 \equiv 16 \pmod 4$, but $4 \not \equiv 16 \pmod{24}$.
However if $n$ and $m$ are relatively prime, then the answer is yes.
This is pretty straightforward to see, as if $a \equiv b \pmod n$ then $n \mid (b-a)$, and if $a \equiv b \pmod m$, then $m \mid (b-a)$. Then one notes (or proves, if it's not clear) that $n \mid (b-a)$, $m \mid (b-a)$, and $\gcd(m,n) = 1$ implies that $mn \mid (b-a)$.
In fact, this is at the edge of a deeper theorem called the Chinese Remainder Theorem, which says roughly that knowing the structure of $x$ mod $n$ and $m$ for $m,n$ relatively prime is equivalent to knowing the structure of $x$ mod $mn$ --- or perhaps with two or three or more moduli all taken together. Look up the Chinese Remainder Theorem on the web and on this site for more.
A: You require $\gcd(m,n)=1$, otherwise
\begin{eqnarray*}
1 \equiv 13 \pmod{4} \\
1 \equiv 13 \pmod{6} \\
\end{eqnarray*}
but 
\begin{eqnarray*}
1 \neq 13 \pmod{24}. \\
\end{eqnarray*}
A: This is true if (and only if) $m$ and $n$ are coprime – which is the case ot two distinct primes. 
This is the statement of the Chinese remainder theorem: if $m, n$ are coprime integers, the map
\begin{align}
\mathbf Z/mn\mathbf Z&\longrightarrow\mathbf Z/m\mathbf Z\times \mathbf Z/n\mathbf Z\\
a\bmod mn&\longmapsto(a\bmod m,a\bmod n)
\end{align}
is an isomorphism.
A: $x \equiv a \mod n $ means $x=a+kn $ for some $k $.  Now $k=qm+r$ for some value of $q $ and $0\le r <m $.  So $x=a +rn + q*mn $ so $x=a+rn\mod mn $.  However we have no idea yet what $r$ is. we just know it is between $0$(inclusively) and $m $(exclusively).
Likewise if $x\equiv a\mod m $ by the same reasoning we know $x\equiv a+sm\mod mn $. We don't know what $s $ is yet.
But $a+sm <mn $ and $a+rn <mn $ and $a+sm\equiv a+rn\mod mn $ so $sm=rn $.
now if $m$ and $n $ are not relatively prime there might be non trivial solutions.  For example maybe $r=\frac m {\gcd (m,n)} $ and $s=\frac n {\gcd (m,n)}$
But if $m $ and $n $ are relatively prime, then $sm=rn $ means $m|r $ and $n|s $.  But $r <m $ and $s <n $ and the only way that can happen is if $sm=rn=0$
