2
$\begingroup$

Why is, for the modulus operation, the notation $A\equiv C \pmod B$ used instead of $A \text{ mod } B = C$? Or alternatively $\text{mod}(A,B) = C$ or, as in many programming languages, $A\text{ } \% \text{ } B = C$.

$\endgroup$
7
  • $\begingroup$ Programmers use mod as a binary operation. Mathematicians use it as a binary relation. $\endgroup$ Jul 20, 2016 at 14:00
  • 1
    $\begingroup$ Because $42\bmod 8=2$, but you also have $42\equiv 34\pmod{8}$. $\endgroup$
    – egreg
    Jul 20, 2016 at 14:01
  • 1
    $\begingroup$ So math $A \equiv B \text{ mod } C$ is programmer $ A \% C = B \% C$ $\endgroup$
    – GEdgar
    Jul 20, 2016 at 14:02
  • $\begingroup$ As said below, mathematicians don't really have much use for mod as a binary operation. But the binary relation (indeed, congruence relation) is useful because, as the name "modular arithmetic" suggests, we can actually do arithmetic mod $n$. That is, if $a\equiv b$ and $c\equiv d$ then $a+c\equiv b+d$ and $ac\equiv bd$ mod $n$. So the integers mod $n$ form a finite number system with addition and multiplication operations. We can then use polynomials to construct all possible finite fields (which computer scientists are interested in too). $\endgroup$ Jul 20, 2016 at 14:10
  • $\begingroup$ @arctictern But mathematicians do indeed perform computations and so they do indeed used normal forms (here the binary operator form of mod). Number theorists use if quite frequently. For example, the fraction $\,a/b\,$ must be in normal form (lowest terms) in order to apply the Rational Root Test. $\endgroup$ Jul 20, 2016 at 15:54

3 Answers 3

4
$\begingroup$

Because $A\equiv C\pmod{B}$ and $A\bmod B=C$ mean very different things. The first just says that $A-C$ is a multiple of $B$, so for a given $A$ and $B$ there are infinitely many different values of $C$ making it true. The second says that $C$ is the unique integer in the set $\{0,1,\ldots,B-1\}$ for which $A-C$ is a multiple of $B$.

To put it a bit differently, the first expresses a relation; it’s analogous to the expression $A=C$ that also expresses a relation between $A$ and $C$. The $\bmod$ in the second is a binary operation on its arguments, analogous to the $+$ in $A+B$: like $A+B$, $A\bmod B$ returns a unique value.

$\endgroup$
1
  • $\begingroup$ In the first one, the $\pmod B$ is not an independent part of the expression, per se, but rather a clarification of $\equiv$. A notation that could've been more intuitive would be $A\equiv_BC$, but unfortunately, that's not how we write things. $\endgroup$
    – Arthur
    Jul 20, 2016 at 14:16
2
$\begingroup$

The notation $m\equiv n\pmod{k}$ means $$ k\mid (m-n) $$ In words, $k$ divides $m-n$.

On the other hand, $m\bmod k$ denotes the unique number $n$ with $0\le n<k$ such that $$m\equiv n\pmod{k}$$ (under a very common convention).

As an example, $42\bmod 8=2$, but we can also write $42\equiv 34\pmod{8}$.

$\endgroup$
4
  • $\begingroup$ Just curiosity: is $m-k\times\lfloor\frac{m}{k}\rfloor$ a proper definition of $m\text{ mod } k$? $\endgroup$
    – drhab
    Jul 20, 2016 at 14:09
  • 1
    $\begingroup$ @drhab There are several conventions about the definition of the binary operation “mod”. I used the simplified setting where $k>0$ is an integer, but it can be generalized and the definition $m-k\lfloor m/k\rfloor$ is frequently used and works also for non integer $k\ne0$. $\endgroup$
    – egreg
    Jul 20, 2016 at 14:11
  • $\begingroup$ But beware that there are two different and possibly reasonable conventions for the meaning when $m$ is negative, and perhaps more choices when $k$ is negative, and the often-horrible choice made by a few programming languages to have the codomain be $1, 2, \ldots, k$ rather than $0, 1, \ldots, k-1$. $\endgroup$ Jul 20, 2016 at 15:50
  • $\begingroup$ @JohnHughes Indeed I warned about possible different conventions. Listing them all might overflow the allotted length for answers. $\endgroup$
    – egreg
    Jul 20, 2016 at 16:34
2
$\begingroup$

The familiar

a % b

or

mod(a, b)

found in many programming languages is a function from the integers to the set $\{0, 1, \ldots, b-1\}$ (or something very similar). That function finds surprisingly little use in mathematics, however, so little that there's no standard notation for it that I know of.

On the other hand, the notion of "equivalence mod $a$", where integers $x$ and $y$ are considered equivalent if their difference $x-y$ happens to be divisible by $a$, comes up a lot, so mathematicians invented a notation for it: they write $$ x \equiv y \bmod a. $$

The "equivalence classes" for this relation, e.g., for $a = 3$, the three sets $$ \{\ldots, -6, -3, 0, 3, 6, \ldots \} \\ \{\ldots, -5, -2, 1, 4, 7, \ldots \} \\ \{\ldots, -4, -1, 2, 5, 8, \ldots\} $$ have the property that each one contains exactly ONE of the numbers between $0$ and $a-1$, so we often use those to indicate which set we're talking about, writing something like

$$ \bar{0} = \{\ldots, -6, -3, 0, 3, 6, \ldots \} \\ \bar{1} =\{\ldots, -5, -2, 1, 4, 7, \ldots\} \\ \bar{2} =\{\ldots, -4, -1, 2, 5, 8, \ldots\} $$

to "name" the equivalence classes. Since there's no easy way, in a computer, to write down an infinite set, programmers decided to use these "names" (dropping the bar) to denote the equivalence class.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.