25
$\begingroup$

I'm more familiar with the notation $a \equiv b \pmod c$, but I think this is equivalent to $a \bmod c = b \bmod c $, which makes it clear that we should put a $=$ instead of $\equiv$.

What's the reason for the change of sign? If it's to emphasize that modular equivalence is a congruence relation, why don't we use the $\equiv$ sign in both notations?

$\endgroup$
  • 1
    $\begingroup$ i guess its so you don'tt have to write $\mod c$ twice. And an equality sign would not be mathematically correct in that setting $\endgroup$ – supinf Aug 14 '15 at 13:25
  • 2
    $\begingroup$ The spacing is (IMHO) better if you use \bmod = binary mod, when you mean the operation that calculates the remainder of a division of one integer by another. $\endgroup$ – Jyrki Lahtonen Aug 14 '15 at 13:44
  • $\begingroup$ Somewhat related (relevant to the expression $a \bmod c$): 'mod' or 'remainder' symbol valid in maths? $\endgroup$ – David K Aug 17 '15 at 20:02

13 Answers 13

29
$\begingroup$
  • I am a human being.
  • You are a human being.

Therefore, I am you: right ? Well, as it turns out, the answer is no. It simply means that we belong to the same class. Likewise, $3\neq7$, but $3\equiv7\bmod4$.

$\endgroup$
  • 3
    $\begingroup$ Pure class of a reply!! $\endgroup$ – Landon Carter Aug 14 '15 at 16:12
  • 24
    $\begingroup$ This reply is incorrect, if you were to make a correct an analogy it would be "Jeffrey's class of living being = Joseph's class of living being" vs "Jeffrey $\equiv$ Joseph (class of living beings". $\endgroup$ – YoTengoUnLCD Aug 14 '15 at 16:18
  • 3
    $\begingroup$ Is the Lucian of 8 hours ago the same Lucian of now, or is this also only an equality modulo the time evolution? $\endgroup$ – Count Iblis Aug 14 '15 at 21:51
  • 6
    $\begingroup$ @YoTengoUnLCD: My idea was to focus on the ambivalence of the verb “to be”. Sometimes it is used to describe or characterize $($such as in the first two sentences above$)$, and at other times it is used to identify $($such as in the third sentence above$)$. In the former situation, it acts like an equivalence sign $(\equiv)$, in the latter is acts like an equality sign $(=)$. $\endgroup$ – Lucian Aug 15 '15 at 2:53
  • 2
    $\begingroup$ The OP isn't claiming $3=7$, the OP is claiming $3(\bmod 4) = 7(\bmod 4)$. $\endgroup$ – Umberto P. Aug 16 '15 at 3:00
13
$\begingroup$

I prefer to use the congruence exclusively (I view the remainder operation as a source of headache even though I realize that it is a necessary evil in computing).

But I use both equal ($=$) and congruent to ($\equiv$) signs together when processing a lengthy calculation in modular arithmetic. My freshman algebra students quickly catch on with my calculations like $$ 12^{3004}\equiv5^{3004}=5^{3000}\cdot 5^4=(5^6)^{500}\cdot 5^4\equiv 1^{500}\cdot5^4=25^2\equiv4^2=16\equiv2\pmod7. $$ IOW, I use $=$ when there is an equality of integers between the steps, and $\equiv$ when I mean a congruence. The power of laws obeyed by congruences is apparent. Checking/following the progress of the calculation is easier this way. Of course, using $\equiv$ all the way is correct also. The $\equiv$ is there as a reminder that in this step we do something that only results in a congruence.

As the students become acquainted with the language of residue class rings, I gradually stop making the distinction between $=$ and $\equiv$ as well as, clarity of context permitting, the distinction between $n$ and $\overline{n}$.

Thinking about what that would look like when done by somebody who is only familiar with binary mod makes me shudder.

$\endgroup$
  • 2
    $\begingroup$ Sorry about the rantish parts. It is rare that I manage to pass up an opportunity to criticize the use of binary mod. IMHO it is a cancer of elementary number theory at worst, and, at best, an attempt to hide (from the innocent students) the fact that calculations now take place in a ring of residue classes as opposed to in the ring of integers. $\endgroup$ – Jyrki Lahtonen Aug 14 '15 at 14:02
  • 2
    $\begingroup$ So some people are now using binary mod in number theory? If so, I support your rant. I use binary mod frequently in software, where the benefits seem worth the headaches, sometimes because it's not always convenient to store the result of a calculation as a residue class rather than as a number, sometimes as a convenient way to decide which arc between two points on a circle is shorter. And therefore I'm familiar with things that make the operator a liability in number theory, such as the fact that people disagree on how to deal with negative operands. $\endgroup$ – David K Aug 14 '15 at 14:25
  • 1
    $\begingroup$ @DavidK: I doubt anybody is using binary mod in number theory. I have just seen many confused computer science majors taking a course in cryptography at our department, and smirking software engineers lecturing me how I need to insert umpteen mod's at selected places in some formula for it to work as a Matlab snippet. I do realize the need for this in software. I have created bugs when I didn't know that for a processor the range of binary mod may vary according to the sign :-) Thankfully such a program will act up sooner rather than later, so debugging is easy (except on the first time). $\endgroup$ – Jyrki Lahtonen Aug 14 '15 at 14:28
  • 1
    $\begingroup$ In software, a chain of eight equivalence relations (as shown in this answer) has to be expressed as a conjunction of eight Boolean expressions such as $1^{500}\cdot 5^4=25^2$. That's the main complication. In my opinion, the correct way to express the $\equiv$ relation in software is as a function of three parameters returning true if the first two parameters are equivalent modulo the third; the actual operation to use is one division with remainder ($(a - b) \bmod c = 0$) rather than two. I suspect your smirking software engineers have been using twice as many mods as needed. $\endgroup$ – David K Aug 14 '15 at 14:56
  • 2
    $\begingroup$ @DavidK: Ah I get what you mean. Certainly. Personally I always define everything precisely before using it, and give good test cases to show what it means (so for binary mod test cases would include negative numbers). So we're fully in agreement then. =) $\endgroup$ – user21820 Aug 18 '15 at 3:34
11
$\begingroup$

It depends on how you define your notation. The standard definition of congruence is $a \equiv b \pmod c$ if and only if $c \mid (b-a)$. The standalone expression $b \pmod c$ is undefined, hence not equal to anything.

On the other hand, some people like to write "$b \bmod c$" to stand for the least nonnegative number $d$ that satisfies $d \equiv b \pmod c$. If you adopt this notation then it is true that $a \equiv b \pmod c$ if and only if $(a \bmod c) = (b \bmod c)$.

$\endgroup$
  • 6
    $\begingroup$ Those "some people" may have gotten it from computer programming, where modulo is a fairly common operator whose semantics resemble those you describe. $\endgroup$ – Kevin Aug 14 '15 at 18:40
  • 3
    $\begingroup$ @Kevin Parenthesis are placed differently in the two cases though. When referring to the binary operator, you don't put a start parenthesis right before the operator. $\endgroup$ – kasperd Aug 14 '15 at 20:09
  • $\begingroup$ Perhaps it looks like some bizarre unary prefix operator...? I mean, (mod 5) does look LISP-ish... $\endgroup$ – Kevin Aug 14 '15 at 20:29
4
$\begingroup$

The difference between the two is as follows:

Note that (in its usual usage) $a \mod c$ is a function that gives a particular answer, and has nothing to do with equivalence relations per se. For example, we might note that $$ \renewcommand{\mod}{\operatorname{mod}} 7 \mod 2 = 1 $$ That is, $7$ has a remainder of $1$ upon division by $2$. What we cannot say is that $$ 7 \mod 2 = 3 $$ because $1$ and $3$ are distinct values. We can say, however, that $$ 7 \equiv 3 \pmod 2 $$ Since both $7$ and $3$ have the same remainder upon division by $2$.


Why is it important? Well, we often make "substitutions" of equivalent values, and writing "mod" every time you make a substitution becomes unwieldy. For example, we can compute: $$ 5*7*9 - 2*3 + 5 + 3 \equiv 1*1*1 - 0*1 + 1 + 1 \equiv 3 \equiv 1 \pmod 2 $$ If we were to write this with mod as an operator, we'd have $$ [5*7*9 - 2*3 + 5 + 3] \mod 2 =\\ [(5 \mod 2)(7 \mod 2)(9 \mod 2) - (2 \mod 2)(3 \mod 2) + (5 \mod 2) + 3 \mod 2] \mod 2 = \\ [(1)(1)(1) - (0)(1) + (1) + 1 ]\mod 2 =\\ 3 \mod 2 = 1 $$

$\endgroup$
  • 1
    $\begingroup$ But $7 \mod 2= 3\mod 2$ (applying the mod operator to both sides, which is what I was asking. $\endgroup$ – YoTengoUnLCD Aug 14 '15 at 13:28
  • $\begingroup$ @YoTengoUnLCD I missed that. I'll change my answer $\endgroup$ – Omnomnomnom Aug 14 '15 at 13:29
  • 1
    $\begingroup$ @YoTengoUnLCD see my latest edit $\endgroup$ – Omnomnomnom Aug 14 '15 at 13:36
  • $\begingroup$ @YoTengoUnLCD note also that computing $a \mod b$ is useful for some who might not want to think about equivalence relations in any capacity (programmers, e.g.). $\endgroup$ – Omnomnomnom Aug 14 '15 at 13:48
  • 1
    $\begingroup$ @fgp thanks for the input, fixed it $\endgroup$ – Omnomnomnom Aug 16 '15 at 13:00
3
$\begingroup$

Equal to means that they are the (exact) same thing. Congruent to means that they have some important property in common, in this case the same remainder when divided by the modulus. The relation, however, must be reflexive, symmetric, and transitive.

$\endgroup$
2
$\begingroup$

We could have $-1 \bmod 2=-1$ and $1\bmod 2=1$, so $1\neq -1$, but nevertheless we have $1\equiv -1 \bmod 2$. So the equality $a\bmod c=b\bmod c$ is not clear, because it depends of the choice of a residue system.

$\endgroup$
  • $\begingroup$ $-1 \mod 2 =1$, as $-1=-1\cdot 2+1$. $\endgroup$ – YoTengoUnLCD Aug 14 '15 at 13:27
  • $\begingroup$ $-1\mod 2=-1$ as $-1=0\cdot 2+(-1)$. $\endgroup$ – Dietrich Burde Aug 14 '15 at 13:28
  • $\begingroup$ The thing is that a mod c is defined to be the remainder of dividing a by c, and by definition, that is a nonnegative number. $\endgroup$ – YoTengoUnLCD Aug 14 '15 at 13:29
  • 2
    $\begingroup$ This depends on the definition. I know many cases where it can be a negative number. It really depends on the choice of a residue system modulo $c$. $\endgroup$ – Dietrich Burde Aug 14 '15 at 13:30
  • $\begingroup$ @YoTengoUnLCD: Many programming languages (and consequently also processors) define the remainder operation to keep the sign of the dividend. This is a consequence of how remainder plays together with integer division (call it DIV). The computer guys want the rule $$a=b*(a\operatorname{DIV} b)+ (a\bmod b)$$ to hold - a good thing. And they also want the rule $$(-a)\operatorname{DIV} b=-(a\operatorname{DIV} b)$$ to hold - another good thing. These two rules force the remainder function to be defined this way. Try it with for example an Intelx86 family processor. $\endgroup$ – Jyrki Lahtonen Aug 14 '15 at 14:16
2
$\begingroup$

I (like most people, I believe) move freely between $=$ and $\equiv$ in the following sense.

Saying $a \equiv b \pmod{n}$ is the same as saying $a = b$ as elements of $ \mathbb Z / n\mathbb Z$. At least this is what I say to my students to keep in mind in case I jump around in my notation.

$\endgroup$
  • $\begingroup$ I would say $\bar a = \bar b$, even though I really find it bothersome to do so, and $a \equiv b \pmod n$. $\endgroup$ – steven gregory Aug 16 '15 at 21:18
2
$\begingroup$

"Why" questions about notation can range into non-mathematical territory: Notation is not always perfectly logical or consistent.

This isn't an explanatory answer, but an extended comment about writing $$ a \equiv b \pmod{c} \tag{1} $$ versus $$ a \bmod{c} = b \bmod{c}. \tag{2} $$

In (1), mod $c$ is grammatically an adverb, modifying the binary relation "is equivalent to". Consistency dictates writing something like $$ a \equiv_{\bmod{c}} b\qquad\text{or}\qquad a \equiv_{c} b. $$ I'm not a historian, but believe the widespread use of the notation (1) at the school level arose in the New Math era of the 1950s. (It's easy to imagine how this "afterthought" notation (mod $c$) would work psychologically for students raised on arithmetic drills involving integers. I haven't a shred of evidence, however, and will keep my speculations private.)

In (2), by contrast, mod $c$ functions grammatically as an adjective, modifying the symbols $a$ and $b$. This is a more sophisticated viewpoint: Instead of relating integers $a$ and $b$ (which are familiar to young students), (2) equates residue classes mod $c$. That's already one reason to avoid (2) in an introductory setting.

To give a completely different reason, writing "$a \bmod{c}$" to denote a residue class is clumsy. The generic equivalence class notation $[a]_{c}$ would be preferable, or even $[a]$ if the modulus $c$ were fixed during the discussion/computation. One does in fact see $[a] = [b]$ in introductory algebra at the university level.

Honestly, even square brackets are cumbersome. (They can also cause perplexing LaTeX errors when Cayley tables are typeset as arrays. Exercise: Why?) Between friends and in private, you might as well denote the residue class simply as "$a$" if the modulus is fixed, so that mod $7$ you have, e.g., $$ 5^{2015} \equiv -(2^{2015}) \equiv -(2^{3 \cdot 671 + 2}) \equiv -4 \equiv 3. $$

Ideally: Mathematical notation conveys concepts concisely, precisely, and consistently across fields and disciplines.

In practice: Changing historical perspectives and notational habits, field-specific conventions and emphases, and computer typesetting capabilities influence the ways we express mathematics in writing. Even sub-specialities of pure mathematics may use mutually-incompatible notation, to say nothing of discussions between pure mathematicians and engineers (say).

The answer to the question at hand may be as banal as "(1) is more compact than (2)" or "that's just the way everyone writes it (in 2015)". The take-away message is: "Mathematical notation is not always logical or consistent, and making notation consistent is much harder than it might first appear."

Answer to Exercise:

If a square-bracketed expression follows a newline command \\ with only white space in between, LaTeX reads the expression as an optional argument, expecting a length.

$\endgroup$
1
$\begingroup$

In more advanced math, you will find number systems where it is not possible (or possible, but not wise) to define $a\mod c$ in an obvious way, while you will be able to write it as $a\equiv b\pmod{c}$.

There is an additional problem with $a\mod c = b\mod c$, which is that it allows for $a\mod c = b\mod d$. But this is hardly ever useful.

There are ways to write it as equality, but it is pedagogically useful to become comfortable with congruence as an instance equivalence relation.

$\endgroup$
  • $\begingroup$ Could you give a example of those number systems? $\endgroup$ – YoTengoUnLCD Aug 15 '15 at 19:03
  • $\begingroup$ Pretty much any commutative ring which is not a field has a non-trivial notion of congruence modulo an ideal. A good example would be $\mathbb Z[\sqrt{-5}]$, where that ring is not a "unique factorization domain," so there is no "good" Euclidean algorithm for choosing remainders. (You can always, if you insist, pick a set of remainders arbitrarily for defining $a\mid b$.) $\endgroup$ – Thomas Andrews Aug 15 '15 at 19:09
1
$\begingroup$

Typically $=$ is used to denote that two objects are equivalent in every single context. It is usually a primitive in logic, defined by textual replacement.

Other symbols, for example $\equiv$, are used for context sensitive equivalence. $9$ is equal to $4$ in the context of $\pmod 5$. Two binary trees may be equivalent in terms of their shape, but not where they are located in memory. A husband and wife may be equivalent for the sake of tax purposes, but not for their respective expectations of each other.

$\endgroup$
1
$\begingroup$

The $a$ in the expression $$a \equiv b \pmod c$$ and the thing you intuitively write as $a \mod c$ in the expression $$a \bmod c = b \bmod c$$ are different kinds of things.

The symbol $a$ denotes an integer—a variable of type $\mathbb{Z}$, as a programmer might say, or an element of the ring $\mathbb{Z}$, as a mathematician might say.

The thing you denote by $a \bmod c$ is an integer modulo $c$—a variable of type $\mathbb{Z}/c\mathbb{Z}$, or an element of the ring $\mathbb{Z}/c\mathbb{Z}$. You can think of an integer modulo $c$ as an "hour" on a "$c$-hour clock," as described at the link above.

There's a natural way to turn an integer $n$ into an integer modulo $c$: you put the clock hand at noon, and then tick it forward $n$ hours. The hour you end up at is the one you call $n \mod c$. A more common notation for it is $[n]_c$, which can be abbreviated to just $[n]$ if it's clear that you're working on a $c$-hour clock.

Saying that the integers $a$ and $b$ are congruent modulo $c$, written $$a \equiv b \pmod c,$$ is the same as saying that the hours $[a]_c$ and $[b]_c$ are equal, written $$[a]_c = [b]_c.$$ In fact, this is how many people define congruence. You should be able to convince yourself, if you think about it long enough, that the hours $[a]_c$ and $[b]_c$ are equal if and only if the integers $a$ and $b$ have the same remainder when divided by $c$, which is another common definition of congruence modulo $c$.

$\endgroup$
  • 1
    $\begingroup$ Try \pmod instead of parentheses with \mod. $\endgroup$ – Hurkyl Aug 16 '15 at 9:42
  • $\begingroup$ @Hurkyl, whoops! Thanks for the tip. The spacing looked fine when I first posted, so I didn't bother looking up which commands I should have been using... $\endgroup$ – Vectornaut Aug 16 '15 at 15:09
0
$\begingroup$

I don't see any problem in writing $a\bmod n = b\bmod n$ as long as one is familiar what it means.

Even "worse" is when dealing with decimal system, we write, for example, $1=0.\dot9$ even though they are not the same series - they merely converge to the same real number.

Now, to the point. We start with ring $\mathbb Z$ (i.e. a structure consisting of integers with familiar addition and multiplication) and fix some natural $n$. Then we define equivalence relation $\equiv$ such that $$ a\equiv b \iff n|b-a$$ Having the fact that one can form quotient set of equivalence classes with respect to $\equiv$, using the properties of $\mathbb Z$ (namely that multiples of $n$ form an ideal) it follows that the quotient set $\mathbb Z/\equiv$ is actually a ring itself and then we use more familiar notation $\mathbb Z/n\mathbb Z$. Very importantly, we get a surjective function $\pi:\mathbb Z\to\mathbb Z/n\mathbb Z$ that sends any $a$ to it's equivalence class $[a]$ satisfying $$\pi(a+b) = \pi(a) + \pi(b),\ \pi(ab) = \pi(a)\pi(b)\quad \text{(i.e. $\pi$ is a ring homomorphism)}$$ So, when we write $a \equiv b\ \pmod n$ we mean that $a$ and $b$ belong to the same equivalence class (which just means that they give the same residue when divided by $n$ in this context) and consequently $\pi(a) = \pi(b)$. We might as well write $\operatorname{mod} n$ instead of $\pi$ and apply convention $a\bmod n = (\operatorname{mod}\ n)(a)$.

Why don't we do it? Because it is tedious to write down calculations that way.

One usual way of writing down calculations is to write $\overline 1,\ \overline 2,\ldots$ for congruence classes when having fixed $n$. For example $\overline 1 = \overline 3$ in $\mathbb Z/2\mathbb Z$, instead of $1\equiv 3\pmod 2$. I wouldn't have problem even if one would write $1=3$ as long as it is clear that these merely represent same elements of the ring $\mathbb Z/2\mathbb Z$, and not equality of integers, just as $1 = 0.\dot 9$ as real numbers, but not as series.

Long story short, how you write depends on the context and most important thing is that it is not ambiguous to the reader.

$\endgroup$
  • 1
    $\begingroup$ Oh, great, now you've opened the door for that old 1=0.9̅9 debate... $\endgroup$ – Dan Henderson Aug 14 '15 at 17:53
  • $\begingroup$ @DanHenderson, hehe, sorry, it wasn't my intention. It was just the first thing that came to mind when thinking about the (ab)use of equality. We could just as well debate whether $1=\frac 1 1$ or not. $\endgroup$ – Ennar Aug 14 '15 at 18:48
  • $\begingroup$ No, $1$ and $0.\dot 9$ are not the same series, but they converge to the same value. $\endgroup$ – Thomas Andrews Aug 15 '15 at 19:11
  • 1
    $\begingroup$ @ThomasAndrews I mention that twice. $\endgroup$ – Ennar Aug 16 '15 at 2:00
0
$\begingroup$

Relating to @Omnomnomnom's answer, I think there is a subtle difference in the mathematical and computer science perspectives to this.

From a computer science perspective, a mod b looks a lot like a % b, which is a distinct operation with a single answer (try typing 7 % 3 into your Python interpreter, and you will always get the same answer).

I generally think of congruency in the following manner:

  1. Congruency: small mod medium ≡ big if and only if small ≡ big mod medium

  2. Equality: big mod medium = small (or in Python, big % medium == small), but the opposite direction does not hold (small mod medium ≠ big).

My experience with this topic is limited to single dimensional modular integer arithmetic used in cryptography, so I cannot speak to any subtleties that may arise in other contexts.

$\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.