1
$\begingroup$

Wiki says:

"...denoted ${\displaystyle a\equiv b{\pmod {n}}.}$

(some authors use $=$ instead of $≡$ ; in this case, if the parentheses are omitted, this generally means that "mod" denotes the modulo operation, that is, that $0 ≤ a < n$)"

Do the parenthesis around mod matter? What it sounds like to me is weather or not three or two lines are used if mod isn't in parenthesis it's an operation. If so then why do we have to distinguish between $\equiv$ and $=$?

$\endgroup$
  • $\begingroup$ In my experience, mathematicians rarely use "mod" as an infix binary operation in mathematical writing. Generally the parentheses are not necessary but they aid clarity a little, especially in complicated modular relationships. If $=$ is used rather than $\equiv$ then you should think about whether mod might be a binary operation. $\endgroup$ – Ian Dec 26 '18 at 13:52
  • $\begingroup$ @Ian Operational mod is common in some mathematical contexts, e,g. see my answer. $\endgroup$ – Bill Dubuque Dec 26 '18 at 17:30
3
$\begingroup$

Mod is not an operation$^1$!

This is a cause of confusion for many students I have started adopting a new notation to clarify this $$17\hspace {.1 cm}\overset{\displaystyle \equiv}{\tiny mod 5} \hspace {.1 cm} 103 $$ The point is that $\mod 5$ is something that modifies the equivalency and not one side or the other. It is no operation. The numbers $17$ and $103$ are in the same category if we are considering what their remainder is after we divide by $5$.

$1:$ Except when it is... The confusion here is that mod IS an operation whenever you talk to a computer scientist/programmer. It's just not an operation in the community of mathematicians.

To confuse the matter: Mathematicians also explore a mapping which is used in a slightly different way from these computer scientists/programmers. If you are interested you can read the comment thread below and I invite you to inquire.

$\endgroup$
  • 2
    $\begingroup$ The operational form $\ a\bmod n\, $ is also widely used by mathematicians. $\endgroup$ – Bill Dubuque Dec 26 '18 at 14:11
  • 1
    $\begingroup$ As an operation? You mean a mapping from $F\times F \to F$? I think of $a \mod n$ as mapping into $\mathbb{Z}_n$. Which in my lexicon is not an "operation." You mean that mathematicians use $a\mod n$ to mean something like computer scientist/programmers saying $a \% n$? I haven't seen this but I believe you. Oh. Ok you softened your comment to say "operational form." I am with you now. $\endgroup$ – Mason Dec 26 '18 at 14:14
  • 2
    $\begingroup$ Yes - see "operational". The attempt by some to denigrate the operational form as non-mathematical is incorrect and misguided. Don't believe everything you read on the web. $\endgroup$ – Bill Dubuque Dec 26 '18 at 14:18
  • 2
    $\begingroup$ @BillDubuque Not $100 \%$ I am understanding what is meant by "operational." I mean it's a mapping into $\mathbb{Z_n}$. No problem from me exploring this mapping $\phi: \mathbb{Z} \to \mathbb{Z_n}$ but in this case ( precisely as the OP hints at) we can say $\phi(x) = \phi(y)$ and put down the notation $\equiv$. Maybe a more complete answer would take on this element of the story. I think I would wait for OP to clarify or respond before I dive deeper into this conversation. $\endgroup$ – Mason Dec 26 '18 at 14:24
  • 1
    $\begingroup$ Haha. Don't believe everything you read on the web! $\endgroup$ – Mason Dec 26 '18 at 14:29
1
$\begingroup$

Parentheses serve to disambiguate the variant notations when used as in the first expression below

$$\begin{align} &a\, =\, b\bmod n\\[.2em] {\rm is\ it}\ \ \ \ &a = (b\bmod n)\ \ \ \ \ {\rm i.e.}\ \ \ a\, =\, {\rm remainder\ of}\ \ b\div n\\[.2em] {\rm or\ is\ it}\ \ \ \ &a = b\!\!\!\pmod{\! n} \ \ \ \ {\rm i.e.}\ \ \ n\ \ {\rm divides}\ \ a-b \end{align}$$

Insisting on the parentheses in the final expression removes the ambiguity. Some authors also believe the ambiguity is removed be using a congruence vs. equal sign, i.e. $\,a\equiv b\mod n\, $ but, alas, beginners often wrongly interpret this in operational form (2nd form above), esp. if it written with less whitespace $\,a\equiv b\bmod n.\,$ Some authors never use the operational form, which does eliminate the ambiguity (but may still prove confusing for beginners who use multiple textbooks).

Remark $ $ Despite some remarks to the contrary, it is worth emphasis that the operational form of $\!\bmod\!$ is widely used in number theory and algebra, e.g. it plays a crucial role in the descent step in the Euclidean gcd algorithm

$$ |a|\ge |b|\,\Rightarrow\, \gcd(a,b) = \gcd(a\bmod b,\, b)$$

Similarly many (inductive) proofs and (recursive) algorithms in number theory and algebra are governed by an analogous (Euclidean) descent (via division with remainder). As such, it proves convenient to have notation for this ubiquitous remainder descent operation.

Also the notation enables expression of fundamental laws that might otherwise be greatly obfuscated. A nice example of this is the $\!\bmod\!$ Distributive Law

$$ ab\bmod ac\, =\, a(b\bmod c)$$

This can be viewed as an operational reformulation of CRT = Chinese Remainder Theorem. Being operational it often greatly simplifies computations. Here's a simple example from here

$$ 3^{\large 1+2n}\!\bmod 12\, =\, 3(3^{\large 2n}\!\bmod 4)\, =\, 3((-1)^{\large 2n}\!\bmod 4)\, =\, 3$$

Below is another example employing polynomial congruences $ $ (equivalent to Lagrange interpolation). If $\,f\,$ satisfies congruences $\ \overbrace{f\equiv 0\pmod{x\!+\!2}}^{\large f(-2)\ =\ 0\ \ \ \ \ \ }\,\ $ and $\,\ \overbrace{f\equiv\color{#0a0}8\pmod{x\!-\!2}}^{\large f(2)\ =\ \color{#0a0}8\phantom{|^{|}}\ }\ $ then

$\qquad\qquad f\bmod x^2\!-\!4\,$ $=\, (x\!+\!2)\Bigg[\dfrac{f}{x\!+\!2}\bmod x\!-\!\color{#c00}2\Bigg]$ $ =\, \underbrace{(x\!+\!2)\left[\dfrac{f(\color{#c00}{2})}{\color{#c00}2\!+\!2}\right] =\, 2(x\!+\!2)}_{\large f\bmod x-\color{#c00}2\,\ =\,\ f(\color{#c00}{2})\,\,\ =\,\ \color{#0a0}8}$

Generally whenever one performs nontrivial calculation it often proves convenient to have notations for normal forms (such as canonical representatives of equivalence classes in quotient objects).

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