# $a \equiv b \mod n \Rightarrow a$ divided by $n$ gives $b$ as a remainder?

In my lecture notes it is written that $a \equiv b \mod n$ with $a, b, n \in \Bbb Z$ could also be understood in the sense that $a$ divided by $n$ gives $b$ as a remainder. I don't see why this should be true though.

Take $a = 5, \ b = 11$. Obviously $5 \equiv 11 \mod 3$, but $5$ divided by $3$ does not give $11$ as a remainder. What am I missing here?

• You are right. Maybe the notes use this convention (ie, assume that $b$ is the remainder). This is not incorrect, because in $\mathbb{Z}/n\mathbb{Z}$ we can select each representant of the equivalence class (arbitrarily) – Martín Vacas Vignolo Dec 28 '17 at 11:27
• If you are ok, you can accept the answer and set as solved. Thanks! – gimusi Dec 29 '17 at 20:52

## 3 Answers

Well $5\equiv11 \pmod 3$ is also the same as $5\equiv 2 \pmod 3$.

From the division algorithm, we know

$$p=s\cdot q+r$$

where $r$ is the remainder and is less than $q$.

Then let $p=5$, $q=3$ and $r=11$ (from your example):

\begin{align} 5&=s\cdot 3+11\\ 3s& = -6 \\ s & = -2 \end{align}

Technically, this still works, though some might argue that the condition $q \gt r$ should exist. Think of congruences as a way to find the remainder, but keep in mind that there's flexibility in that definition.

I think you're confusing

• $a\equiv b \mod n$, also denoted $a\equiv b \pmod n$, which means that $a$ and $b$ have the same remainder when divided by $n$;
• and $a\bmod n=b$ (note the different spacing between $a$ and $\bmod$!), which means that the remainder of $a$ divided by $n$ is $b$, which is often implemented in CAS as the function mod(a;n) or something similar.

Since

$$a\equiv b \pmod n \iff a= kn+b \iff a=hn+r \ \land \ b=jn+r$$

the statement is true in the sense that $a$ divided by $n$ gives $b$ as a remainder mod n (and viceversa).

In your example:

$$5\equiv 11 \pmod 3 \iff 5= -2\cdot3+11\iff5=1\cdot3+2\ \land \ 11=3\cdot3+2$$