Modular Arithmetic Misconceptions

This is part of a series on common misconceptions.

Is this true or false?

If \( a \equiv b \pmod m\) and \( a\equiv b \pmod n,\) then \( a\equiv b \pmod{mn}.\)

Why some people say it's true: This is part of the Chinese remainder theorem.

Why some people say it's false: You can multiply \(a\) and \(b,\) but you can't multiply the moduli.

The statement is \( \color{red}{\textbf{false}}\).

Proof:

In fact the statement is only true for relatively prime integers \(m\) and \(n;\) this is a consequence of the "uniqueness" part of the Chinese remainder theorem. To see directly that it is true if \(m\) and \(n\) are relatively prime, notice that \( m|(a-b)\) and \( n|(a-b),\) so \( \text{lcm}(m,n)|(a-b).\) If \(m\) and \(n\) are relatively prime, \( \text{lcm}(m,n)=mn,\) so \( mn|(a-b),\) so \( a\equiv b \pmod{mn}.\)

This proof makes the general result clear: if \(a\equiv b \pmod m\) and \(a\equiv b \pmod n,\) then \( a\equiv b \pmod{\text{lcm}{\small(m,n)}}.\) (The converse is also true.)

For example, if \( a=13,b=1,m=4,n=6,\) then \( 13\equiv 1 \pmod 4\) and \( 13\equiv 1 \pmod 6,\) but \(13\not\equiv 1 \pmod{24}.\) So this is a counterexample to the original statement. \(\big(\)Note that \( 13\equiv 1 \pmod{12}\) and \( 12=\text{lcm}(4,6).\big)\) \(_\square\)

Rebuttal: If \(m\) and \(n\) are factors of \( a-b,\) then they both show up in the factorization of \( a-b,\) so their product shows up too. So \(mn|(a-b).\)
Reply: This is only true if \(m\) and \(n\) are relatively prime. In the above example, \[ 13-1 = 12 = {\bf 4} \cdot 3 = {\bf 6} \cdot 2, \] but \( 4\) and \( 6\) don't show up in the same factorization of \( a-b.\)

---

Rebuttal: The result is true in lots of cases. For instance, if \( m\) and \(n\) are distinct primes, the result is true.
Reply: This is correct, but the statement is still false, since it does not hold for all \(m,n.\)

Is this true or false?

If \( a \equiv b \pmod m,\) then \( a= b + m.\)

Why some people say it's true: If \( a=b+m,\) then \( a\equiv b\pmod m.\)

Why some people say it's false: There are more than two numbers congruent to \( b\pmod m.\)

The statement is \( \color{red}{\textbf{false}}\).

Proof:

The converse is true, but the statement is false: if \( a\equiv b \pmod m\) and \( b\) is fixed, there are infinitely many choices for \( a. \) For example, if \( b=1\) and \(m=3,\) then \(a\) might be \(b+m=1+3=4,\) but it could also be \( 7,\) or \(1,\) or \(-998.\) Any number of the form \(1+3k,\) \(k\) an integer, will work. \(_\square\)

Rebuttal: Here is an example: If \( a=7,b=3,m=4,\) then \( a\equiv b\pmod m \) and \(a=b+m.\)

Reply: The conclusion is true for some values of \(a,b,m,\) but not all of them. So the statement is false.

Is this true or false?

If \( a \equiv b \pmod m,\) then \( na \equiv nb \pmod{nm}.\)

Why some people say it's true: Multiply everything by \( n.\)

Why some people say it's false: It makes sense to multiply both sides of the equation by \( n,\) but changing the modulus as well is different.

The statement is \( \color{blue}{\textbf{true}}\).

Proof:

Convert to statements about divisibility. Start with \( a\equiv b \pmod m;\) this means \( m|(a-b).\) So \( mk=a-b\) for some integer \( k.\) Now multiply both sides by \(n:\) \(mnk = n(a-b) = na-nb,\) so \[ mn|(na-nb) \implies na \equiv nb \pmod{mn}.\ _\square \]

Rebuttal: This is only true mod \( m,\) not mod \( nm.\)

Reply: It is also true mod \( m,\) but this statement is stronger. The proof is different, too: instead of working mod \( m,\) it is necessary to convert to statements about integers.

Is this true or false?

If \( na \equiv nb \pmod m\) and \( n \ne 0,\) then \( a \equiv b \pmod m.\)

Why some people say it's true: It is true for integers, so it should be true for the integers mod \( m.\)

Why some people say it's false: Dividing by \( n \) may not be allowed mod \( m.\)

The statement is \( \color{red}{\textbf{false}}\).

Proof:

If \( m\) and \( n\) are not relatively prime, the statement is not true for all \( a,b.\) Converting \( na \equiv nb \pmod m\) to a divisibility statement yields \( m|n(a-b),\) but concluding that \( m|(a-b) \) requires that \( m \) and \( n \) are relatively prime.

A counterexample when \(m\) and \( n\) are not relatively prime is \( m=4,n=2,a=1,b=3.\) Then \( 2\cdot 1 \equiv 2 \cdot 3 \pmod 4,\) but \( 1 \not\equiv 3 \pmod 4.\) \(_\square\)

Rebuttal: Just multiply both sides by \( \frac1{n}.\)

Reply: The multiplicative inverse \( \frac1{n}\) does not exist mod \( m\) unless \( m\) and \( n \) are relatively prime.

Is this true or false?

If \( na \equiv nb \pmod {nm},\) and \( n \ne 0,\) then \( a \equiv b \pmod m.\)

Why some people say it's true: Divide everything by \( n.\)

Why some people say it's false: Dividing by \( n \) is not allowed mod \( nm.\)

The statement is \( \color{blue}{\textbf{true}}\).

Proof:

Convert the first congruence to a divisibility statement: \( nm|(na-nb),\) or \( nm|n(a-b).\) So there is an integer \(k\) such that \[ nmk=n(a-b). \] Since \(n\ne 0,\) we can cancel \(n\) from both sides, so \(mk=a-b,\) so \( m|(a-b),\) so \(a\equiv b \pmod m.\) \(_\square\)

Rebuttal: You can't cancel \(n\) unless it is relatively prime to the modulus.

Reply: This is true in general, but here we are changing the modulus after canceling. The statement is still provable by converting it to a statement about integers, where cancellation of any nonzero integer is allowed.

See Also

• List of Common Misconceptions