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$
  • $\begingroup$ Programmers use mod as a binary operation. Mathematicians use it as a binary relation. $\endgroup$ – arctic tern Jul 20 '16 at 14:00
  • 1
    $\begingroup$ Because $42\bmod 8=2$, but you also have $42\equiv 34\pmod{8}$. $\endgroup$ – egreg Jul 20 '16 at 14:01
  • 1
    $\begingroup$ So math $A \equiv B \text{ mod } C$ is programmer $ A \% C = B \% C$ $\endgroup$ – GEdgar Jul 20 '16 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$ – arctic tern Jul 20 '16 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$ – Bill Dubuque Jul 20 '16 at 15:54
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.

| cite | improve this answer | |
$\endgroup$
  • $\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 '16 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}$.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Just curiosity: is $m-k\times\lfloor\frac{m}{k}\rfloor$ a proper definition of $m\text{ mod } k$? $\endgroup$ – drhab Jul 20 '16 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 '16 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$ – John Hughes Jul 20 '16 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 '16 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.

| cite | improve this answer | |
$\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.