6
$\begingroup$

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$?

  • 0
    @Arturo Note that I have rolled back your edit to the OP's original notation since the question may depend upon that, e.g. the OP might be encountering precisely that (sloppy) notation. Only the OP can change this if need be, since we don't know what is correct.2012-03-16

3 Answers 3

10

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}$.)

0

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,

  • 0
    @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.2012-03-16
-2

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