2
$\begingroup$

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?

$\endgroup$
0
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – rjm27trekkie Feb 27 '18 at 1:16
0
$\begingroup$

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

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

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.

$\endgroup$
0
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.