Multiplication of Moduli in Modular Congruences

Question

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?

Answer 1

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.

Answer 2

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*}

Answer 3

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.

Answer 4

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