# 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?

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.

• If I might add to this question a bit. This works when i have the $a^5$ and a for a and b but if i take b = 1 it clearly doesn't work since $2^4 \equiv 6 \pmod{10}$ but $2^5 \equiv 2 \pmod{10}$ which makes sense since with a not coprime to 10 when a=2 it wouldn't be invertible mod 10. How is one to catch this beforehand though and what makes it work when it's multiplied on both sides by a? – rjm27trekkie Feb 27 '18 at 1:16

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

• Understood. Otherwise, is the conjecture correct given that (m,n) = 1? – rjm27trekkie Feb 27 '18 at 1:05
• That's right ... – Donald Splutterwit Feb 27 '18 at 1:09

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.

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