# Congruent Modulo $n$: definition

In an Introduction to Abstract Algebra by Thomas Whitelaw, he gives examples of the congruence mod operation, such as $13 \equiv5 \pmod4$, and $9 \equiv -1 \pmod 5$. But when I first learned about the modulo operation my junior year, I would have told you that $13 \equiv 1 \pmod 4$, and that $9 \equiv 4 \pmod 5$.

Is this just a difference in the definition of modulo? Or is this pretty typical (to not take it to the largest factor, or one over)?

-
It's the difference between mathematics (Whitelaw) and computer science (junior year). –  Gerry Myerson Mar 12 '13 at 2:41
@GerryMyerson: good answer! –  MITjanitor Mar 12 '13 at 2:41
In other words, you're thinking of modulo as an operation, like $+$. Your book is thinking of it like a relation, like $=$. –  Jack M Mar 12 '13 at 10:24

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

-
Love it Amy. +++ –  Babak S. Mar 12 '13 at 18:18

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 \mod 4 = 1$, or even $13\%4=1$. (In particular, none of that equivalence relation / only up to equivalence stuff).

-
+1 for describing the difference between a mathemetician and computer scientist view of the world –  Code-Guru Mar 12 '13 at 2:54

Congruence, as described in your algebra book, is a relation. We have $a\equiv b\pmod{m}$ precisely if $m$ divides $a-b$. Thus the following are all true: $17\equiv 2\pmod{5}$, $17\equiv 7\pmod{5}$, $17\equiv -13\pmod{5}$, and so on.

You met the modulo operator, or operation, in your third year, probably in a Computer Science course. There, some people write $a\bmod m$ for the remainder when $a$ is divided by $m$. Thus $a\bmod m$ is an object, a number. So $a\bmod m=b$ means that $b$ is the remainder when $a$ is divided by $m$.
To make things more confusing, sometimes they write $a\bmod m\equiv b$ to mean the same thing.

Thus $17\bmod 5=2$ is true, while $17\bmod 5=12$ is false, since $12$ is not the remainder when $17$ is divided by $5$.

Remark: The congruence notation of your algebra book goes back to Gauss. For about $150$ years, congruence modulo $m$ was a relation, and it still is in almost all of mathematics.

It would have been nice, when Computer Science people were looking for a notation for the remainder, if they had chosen a notation that was not so close to standard notation for something else. And what's worse, the "something else" is related, guaranteeing decades of student confusion. Luckily, in most computer languages, "mod" is not used for the remainder operator.

That was a little harsh. So in a spirit of cooperation, I will use both notions in a single sentence. If $m$ is a positive integer, then $$a\equiv b\pmod{m} \quad\text{if and only if}\quad a\bmod m=b\bmod m.$$

-

Yep, in mathematics, we say that the modulo operation separates the integers into congruence classes. So (mod 3) gives us 3 classes:

• $\{ \ldots , -3, 0, 3, \ldots \}$

• $\{ \ldots , -2, 1 ,4 \ldots \}$

• $\{ \ldots , -1, 2, 5 \ldots \}$.

Since -1 and 5 are in the same class, we may say that $-1 \equiv 5 \, ( \! \! \! \mod 3 )$.

-