This is not a technical question, but a question on whether we can use a particular notation while doing modular arithmetic.

We write $a \equiv b \bmod n$, but is it right to write $a \bmod n \equiv b$?

  • 4
    $\begingroup$ No, isn't right it. There is also the issue of potential confusion with the $a \bmod n=r$ of Computer Science. $\endgroup$ – André Nicolas Mar 16 '12 at 19:45
  • 1
    $\begingroup$ What's the difference in the two notations? Should we not have $\equiv$ sign when relating an integer with an equivalence class? $\endgroup$ – Jalaj Mar 16 '12 at 19:49
  • $\begingroup$ Lol Andre, you wrote "isn't right it" instead of "it isn't right". But I agree, it isn't right, see my answer. $\endgroup$ – Patrick Da Silva Mar 16 '12 at 19:54
  • $\begingroup$ (Looks for Patrick's answer.) $\endgroup$ – Joe Mar 16 '12 at 19:56
  • $\begingroup$ @Jay : Look again. =) (It wasn't there at the moment) $\endgroup$ – Patrick Da Silva Mar 16 '12 at 20:00

We have two different, but related, notions:

  1. The equivalence relation "congruent modulo $n$".

    Let $n$ be a fixed integer. If $a$ and $b$ are integers, we say that "$a$ and $b$ are congruent modulo $n$" if and only if $n|b-a$. We write it this way: $$a\equiv b\pmod{n}.$$ The symbol $\equiv$ is read "is congruent to" (as opposed to the symbol $=$ which is read "is equal to").

  2. The binary operator $\bmod$.

    Let $n$ be a positive integer. If $a$ is an integer, then $a\bmod n$ is the remainder (from a distinguished set, see below) of dividing $a$ by $n$. This is read "$a$ modulo $n$".

    In mathematics, $a\bmod n$ is usually defined to be the unique integer $r$ such that $a=nq + r$ for some integer $q$ and $0\leq r \lt n$. In other areas, such as computer science (and sometimes in mathematics), one often requires that $a\bmod n$ be the unique integer $r$ such that $-\frac{n}{2}\lt r\lt \frac{n}{2}+1$ and $a-r$ is a multiple of $n$.

    More generally, one may specify a "distinguished set of remainders modulo $n$", a set $R_n=\{a_0,\ldots,a_{n-1}\}$ such that every integer $x$ is congruent modulo $n$ to one and only one element of $R_n$, and define $\bmod$ as the operator such that $x\bmod n$ is the unique element of $a\in R_n$ such that $x\equiv a\pmod{n}$.

    The operator $\bmod$ is like any other infix notation operator such as $+$; we write $2+3 = 5$, because the result of doing the operation $+$ to $2$ and $3$ is $5$. We write "$a\bmod n = b$" to signify that $b$ is the result of performing the operation "modulo $n$" to $a$.

The two notions are related in that if $a\bmod n = b$, then $a\equiv b\pmod{n}$. The converse does not hold in general, since we have, for example, $5\equiv 9\pmod{4}$, but $5\bmod 4 = 1\neq 9$.

Writing "$a\bmod n \equiv b$" confuses the two notions and is syntactically incorrect. You should use $=$, not $\equiv$. With $=$, it would be "mathematically correct" if and only if $b$ is the result of computing $a\bmod n$ (so $5\bmod 4 = 5$ would be wrong, but $5\bmod 4=1$ would be correct).

Writing $a\equiv b\bmod n$ also invites confusion of the two notions.

(Note, however, that "$a\bmod n \equiv b \pmod{n}$" would be syntactically correct, and would be mathematically correct if $a\equiv b\pmod{n}$.)


In computer science when we write $a \, \% \, n == b$, $\%$ is an operator/function/whatchamaycallit that acts on $a$ to return something, but in mathematics, writing "$\pmod n$" means that we are looking at an equality that works in some quotient of a group/ring/$(\dots)$. For instance, writing $$ a \pmod n \equiv b $$ has no mathematical definition, because on the left "side" of the congruence we have $a \pmod n$ which is some equivalence class of integers (I assume), but on the right hand side we have an integer (I assume again), and then you want them to be "equiv" ($\equiv$ is \equiv in TeX) in some sense, but then again not defined. (It works in computer science, but then again... well.) The standard way of writing things in mathematics is that $$ a \equiv b \pmod n $$ meaning that "$a$ and $b$ are equivalent up to an element of the ideal generated by $n$, that is, an $n$-multiple". You should read this as $$ [[ a \equiv b ]] \pmod n $$ in the sense that $\pmod n$ is "something you apply to the equation", i.e. "you quotient".

Hope that helps,

  • $\begingroup$ A few remarks. First, note that the OP did not write $a \pmod n \equiv b$, but something very different. Second, $a\equiv b \pmod n$ does not always imply that $a,b$ denote equivalence classes, e.g. it is often introduced in elementary number theory classes before quotient rings are studied (just as it was originally by Gauss). I cannot make any sense of your final displayed equation. $\endgroup$ – Bill Dubuque Mar 16 '12 at 20:31
  • $\begingroup$ Minor comment: $a \% n$ is used in programming (C++ language and alike). In computer science, the algorithmic notation is often $a \bmod n$ (also $a \operatorname{rem} n$). $\endgroup$ – user2468 Mar 16 '12 at 20:55
  • $\begingroup$ What I mean by the final equation is maybe not that clear... I don't like my answer that much after all. But what I tried to say was that when we use mod n in number theory it's usually something like $$ [[a \equiv b \equiv c \equiv d \equiv e]] \pmod n $$ and we remove the brackets all the time, because it is clear from the context that putting the $\pmod n$ at the end of the equalities means "Read everything mod n". $\endgroup$ – Patrick Da Silva Mar 16 '12 at 22:23
  • $\begingroup$ @Bill Dubuque : I know that $a \equiv b$ modulo $n$ does not mean that $a$ and $b$ are equivalence classes, but the "equality" stands between equivalence classes, that's what I mean. In what means do you distinguish $a \pmod n \equiv b$ and $a \mod n \equiv b$? I thought the parenthesis didn't mean much here. $\endgroup$ – Patrick Da Silva Mar 16 '12 at 22:25

It is often correct. $\TeX$ distinguishes the two usages: the \pmod control sequence is for "parenthesized" $\pmod n$ used to contextualize an equivalence, as in your first example, and the \bmod control sequence is for "binary operator" $\bmod$ when used like a binary operator (in your second example).

But in the latter case, you should use $=$, not $\equiv$. $7\bmod4 = 3$, and the relation here is a numeric equality, indicated by $=$, not a modular equivalence, which would be indicated by $\equiv$.


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.