# Modular Arithmetic Misconceptions

This is part of a series on common misconceptions.

#### Contents

## Congruences Modulo Products

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

## Do congruent integers differ by the modulus?

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.

## Modular Multiplication on Both Sides

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.

## Cancellation and Modular Multiplication

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.

## Cancellation and Modular Multiplication - Part 2

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

**Cite as:**Modular Arithmetic Misconceptions.

*Brilliant.org*. Retrieved from https://brilliant.org/wiki/modular-arithmetic-misconceptions/