Why is congruence sign $A\equiv B\pmod{C}$?

Question

Why is congruence sign $A\equiv B\pmod{C}$?

Wouldn't it be more natural to use $A \equiv_{C} B$ instead?

The former notation suggests that you take B and make some operation on it (like in case of division or multiplication notation B / C and B * C), while in fact you take A and B and state a relation between them with respect to C?

Answer 1

It seems that the notation was invented by Gauss, who gave the following reasoning for it (copied from the English translation found in this paper¹):

If a certain number, which we will call the modulus, measures the difference of two numbers, we will call these numbers congruent to the modulus, if not, incongruent. In the first case one of the two numbers will be called the residue of the other, in the second case, a nonresidue. E.g. 32 and 11 will be called congruent to the modulus 7, because the difference of these numbers, 21, is divisible by 7.

Denoting congruent numbers by a sign is very useful for abbreviating calculations: thus, because of the analogy with equality between numbers, we will use as a sign, this sign ≡, the modulus can be added in brackets to avoid ambiguity if it is considered necessary.

(Emphasis mine).

Thus, it seems the original reason behind this longish notation was actually a space saving device, since you can omit explicitly mentioning the modulus if it's clear what $\text{mod}$ you're working with. This is often the case as you can see in many worked modular arithmetic problems. Moreover, when working symbolically, where results are true for e.g. any prime modulus, having to write $\equiv_p$ may distract the reader from the proof itself.

¹ _{"Modular arithmetic before C.F. Gauss: Systematizations and discussions on remainder problems in 18th-century Germany", Maarten Bullynck}

Answer 2

A subjective answer.

First there is the calculation : $a\mod{c}=b$ with a true equal sign, where $a\in\mathbb Z$ is reduced to the remainder $b\in\{0,1,...c-1\}$ via the Euclidian division by $c$.

And then there is the equivalence $a\equiv b\pmod{c}$, where $(a,b)\in\mathbb Z^2$ meaning that classes $\bar a=\bar b$ are equal in $\mathbb Z/c\mathbb Z$.

I feel that $\equiv_c$ is some kind of compromise between these two, and that one expects $b$ to be the reduced representative $0\le b\le c-1$ in this case. This is kind of going half way to the true meaning of equivalence classes.

Although note that in chaining calculations, we often omit the modulo except for once at the end :

$a\equiv b_1 \equiv b_2\equiv b_3 \pmod{c}$

Answer 3

The main reason for the notation is:

Because of inertia.

A notation, once established, tends to stay the same. This is the notation Gauss used, so it's the notation that his students used, and their students, etc., etc. Not all math notations are optimized for clarity. Don't get me started on $\sin^n x$, and how that means something different if $n=-1$.

That said, the second part of the answer is:

Both notations are used, and considered correct.

Plenty of elementary number theory books introduce the subscript notation as an alternative. It doesn't get used very often. I find that I use it more in my informal scratchwork, as a compromise between the full, usual notation, and simply omitting the modulus.

Simply omitting the modulus is also permitted, in cases where ambiguity will not result, but hardly anybody does it, at least in work that they're going to show anyone else. Why? I think, ultimately:

It has become part of the culture of number theory.

Understanding and using this somewhat clunky notation has just become part of what it means to get to know the subject, along with abandoning the computer science notation (and conception) of "$b \bmod C$" as an operator that takes an integer $b$ and returns the least non-negative residue modulo $C$. Is this confusing? Yes, a little. Is this a shibboleth that sets number theorists apart from non-initiates? Yes, kind of. Is it helpful, when teaching the subject, to sometimes use the more natural subscript notation, and to directly address the awkwardness of the other? Absolutely.

Answer 4

"More natural" ? -- it would depend on a definition "natural". There is hardly any.

When I was writing my first papers (I was a student at the time), Aleksander Pełczyński gave me a good advice about notation: try to keep your notation linear (meaning: avoid lower and upper indices). A century and a half before that time, Carl F. Gauss obeyed the notational linearity principle.

(This is not an end of the story but enough for one answer)