Congruent Modulo $n$: definition

Mathematically, congruence modulo $n$ is an equivalence relation. We define:

$$a\equiv b \pmod n \iff n\mid (a - b)$$

Equivalently: When working in $\pmod n$, any number $a$ is congruent $\mod n$ to an integer $b$ if there exists an integer $k$ for which $\;nk = (a - b)$.

Now, let's compare the "discrepancies" in the equivalences you note (which are, in fact, all true):

$$13 \equiv \color{blue}{\bf 1} \pmod 4 \iff 4\mid (13-1) \iff 4\mid 12\; \checkmark$$ $$13\equiv \color{blue}{\bf 5} \pmod 4 \iff 4\mid (13-5) \iff 4\mid 8 \;\checkmark$$

• Note, indeed, that $\color{blue}{\bf 5 \equiv 1} \pmod 4$ since $4\mid(5 - 1) = 4$ $$ $$

$$9 \equiv \color{blue}{\bf 4} \pmod 5 \iff 5 \mid (9-4) \iff 5\mid 5 \;\checkmark$$ $$9 \equiv \color{blue}{\bf -1} \pmod 5 \iff 5 \mid (9 - (-1)) \iff 5\mid 10 \;\checkmark$$

• And again, note that $\color{blue}{\bf4 \equiv -1} \pmod 5$ since $5\mid(4-(-1)) = 5$ $$ $$

It is often customary to express equivalence modulo $n$, by choosing $b$ in $\;a \equiv b \pmod n\;$ to be such that $0 \leq b \lt n$. But this choice is simply a representative of all the numbers which belong to the same equivalence class, denoted $[b]$, $\pmod n$:

E.g. If $n = 4$, then one of the following holds: $$a \equiv b \pmod 4 \iff \begin{cases} a, b \in [0] = \{4k + 0\mid k\in \mathbb Z\} = \{\cdots, -8, -4, 0, 4, 8, 12,\cdots\} \\ \\ a, b \in [1] = \{4k + 1\mid k \in \mathbb Z\} = \{\cdots, -7, -3, 1, 5, 9, 13,\cdots\} \\ \\ a ,b \in [2] = \{4k + 2\mid k \in \mathbb Z\} = \{\cdots, -6, -2, 2, 6, 10, 14,\cdots\} \\ \\ a, b \in [3] = \{4k + 3\mid k \in \mathbb Z\} = \{\cdots, -5, -1, 3, 7, 11, 15, \cdots\} \end{cases} $$

All the equations you wrote up there are correct. $13 \equiv 5 \equiv 1 \equiv 1 + 4k \pmod 4$ for any integer $k$. Computer scientists tend to say that the 'modulus operation' returns the smallest integer between $0$ and what you're modding out by. Mathematicians take a slightly higher viewpoint, saying two numbers are considered the same if their difference is divisible by what you're modding out by.

But I would expect a different notation. Mathematically, $13 \equiv 5 \equiv 1 \equiv 1 + 4k \pmod 4$. In computer science, I would expect to see $13 \bmod 4 = 1$, or even $13\%4=1$. (In particular, none of that equivalence relation / only up to equivalence stuff).