I am trying to write the Euclidean algorithm in the following way:
$A = \lfloor A \div B \rfloor \times B + (\text{remainder of}) \: A \div B $
Now is there any symbol I can use to say "remainder of A $\div$ B"? I know that in the C programming language there is the operator % for modulus; is that a valid symbol in maths? Can I write A % B? Or is there some other way?
$\endgroup$ 136 Answers
$\begingroup$Per request, I post my comment(s) as an answer, and add some further remarks.
The notation $\, a\bmod b\, $ denotes the remainder when dividing $\,a\,$ by $\,b\,$ using the division algorithm, e.g. $\, a\bmod 2 = 1\,$ means $\,a = 2n+1\,$ for an integer $\,n,\,$ i.e. $\,a\,$ is odd. $\,a\,\%\,b\, :=\, a\bmod b\,$ is notation sometimes found in programming languages (see below).
The same notation is used in other rings that have an analogous (Euclidean) Division Algorithm, e.g. polynomials with coefficients over a field, e.g. the Polynomial Remainder Theorem: $\,f(a) = f(x)\bmod x\!-\!a,\,$ or higher-degree forms like $\,f(i) = (f(x)\bmod x^2\!+\!1)\bmod x\!-\!i$.
Also $\!\bmod\!$ is used as a ternary relation (vs. above binary operation) when dealing with congruences, i.e. $\ a\equiv b\pmod{\! n}\iff n\mid a-b\,$ (an equivalence relation for a fixed modulus $\,n).$
These two denotations of $\!\bmod\!$ are related as follows (cf. proofs here or here)
$$ a\equiv b\!\!\!\pmod{\!n}\iff a\bmod n\, =\, b\bmod n$$
so $\,a\bmod n\,$ serves as a normal form or canonical representative for the entire equivalence class $\,[a]_n = a + n\Bbb Z\,$ of all integers $\,\equiv a\pmod{\!n}$. So the above displayed equivalence means that testing congruence of integers reduces to testing equality of their normal forms (= remainders $\!\bmod n),\,$ just as we can test equivalence of fractions by testing equality of their least-terms normal forms. Similarly we can view the remainder as a "least terms" rep: it is the least nonnegative integer in the class $[a]_n$ of all integers congruent to $\,a\,$ modulo $\,n.\,$
The operational use of mod is often more convenient in computational contexts, whereas the relational use often yields more flexibility in theoretical contexts. The difference amounts to whether it is more convenient to work with general equivalence classes vs. canonical / normal representatives ("reps") thereof. For example, it would be quite cumbersome to state the laws of fraction arithmetic if we required that all fractions to be in normal (reduced) form, i.e. in lowest terms. Instead, it proves more convenient to have the flexibility to work with arbitrary equivalent fractions. For example, this allows us to state the fraction addition rule in very simple form by first choosing convenient reps having a common denominator.
Analogously, in modular arithmetic the canonical remainder $\,a\ {\rm mod}\ m\,$ may not be the most convenient choice of representative of the equivalence class $\,[a]_n =\, a + n\,\Bbb Z.\,$ For example, casting out elevens exploits that $\ {\rm mod}\ 11\!:\ 10\equiv -1\,\Rightarrow\,10^{\large k}\equiv (-1)^{\large k}\equiv \pm1,\,$ which involves choosing a rep of least magnitude $\,\color{#c00}{\bf -1}\,$ vs. $\,\color{#0a0}{10}\in [10]_{11}\! = \{\ldots,\, -23,-12,\color{#c00}{\bf -1},\color{#0a0}{10},21,\,\ldots\}.\,$ Or, as here we can choose reps that conveniently make a quotient be exact when computing modular fractions, e.g. $\!\bmod 11\!:\,\ 9/13\equiv -2/2\equiv -1.\,$Hence, analogous to fraction addition, we chose reps which simplified arithmetic. Using least magnitude reps often simplifies other computations too, e.g. it can halve the number of steps in the Euclidean algorithm. Thus the use of congruence classes (vs. canonical reps) provides much greater flexibility, which may yield great simplifications - not only computationally, but also theoretically, which becomes clearer when one studies quotient rings, which yield (algebraic) structure reifications of the the congruence rules = compatibility of congruences with addition and multiplication).
See here for much further discussion of the mod operator vs. the mod congruence relation.
Beware that some authors omit the parentheses in $\, a\equiv b\pmod{\!n}$ instead writing them as follows $\,a\equiv b\mod n\ $ or $\ a = b\mod n,\ $ using \mod vs. \pmod in $\TeX$. These might easily be confused with $\,a = b\bmod n\,$ i.e. $\,a = (b\bmod n),\,$ so one should keep in mind such possible ambiguities in contexts where both forms of $\!\bmod\!$ are in use. See here for more on this.
The name '%' for the normal form $\!\bmod\!$ operation (as in the C programming language) has not percolated to the mathematical community as far as I can tell. I recall many questions on sci.math regarding the meaning of $\rm\, a\,\%\, b.\, $ As such, if you use this notation in a mathematical forum then I recommend that you specify its meaning. This would not be necessary for $\!\bmod\!$ since that notation is ubiquitous in mathematics (currently more so for congruence than operator form). Be aware, however, that some mathematicians look down on the operational use of mod in the case when it would be more natural to use the congruence form. Apparently the mathematical Gods do too, since doing so can make some proofs quite more difficult (much more so than the above simple case of fraction addition).
$\endgroup$ 12 $\begingroup$It's fine to use $A \% B$ for the remainder of $A$ when divided by $B$, provided that you explain what you are using the percent symbol to mean.
It is fairly common in mathematics to need to introduce a symbol to conveniently express something you're going to use: it is infeasible and undesirable to have standardized notation for absolutely everything.
And since this operator is used infrequently in mathematics, there hasn't been standardized notation for it. $A \bmod B$ is probably the most common notation I've seen for it, although it's mildly abusive and possibly a little confusing, since the $\bmod$ symbol is used in other ways too.
Do not just invent notation without explaining your meaning, though. Doing that is not accepted. Also, you should clearly point out how you're normalizing the remainder: e.g. that you are insisting that it is an integer in the interval $[0, |B| - 1]$.
$\endgroup$ 4 $\begingroup$You can write the remainder, mathematically, as $A\; \text{mod}\; B$, which is fairly well-understood to mean the remainder of $A \div B$.
ADDED: In programming, you are correct, $A\,\%\,B$, in many languages, is the operation that returns the remainder when dividing $A$ by $B$. Within mathematics, % is not an accepted notation for this purpose.
$\endgroup$ 3 $\begingroup$At some time, the use of "mod" in mathematics was restricted to congruences:
$$a\equiv b \pmod n \iff n \, | \, a - b$$
Thus you have always, when $r$ is the remainder of the division $a/b$:
$$a \equiv r \pmod b$$
However, the notation "$a \;\mathrm{mod}\; b$" is now quite widespread, probably with the help of notations from programming languages (it's written exactly this way in Pascal, for instance). It has also been used in very well known computer science books, like "Concrete Mathematics", where it proved to be very useful in mathematical formulas as well.
$\endgroup$ 3 $\begingroup$One can also use the "symmetrical" notation $$ A = \left\lfloor {A/B} \right\rfloor B + \left\{ {A/B} \right\}B $$ where $\left\{ x \right\} = x - \left\lfloor x \right\rfloor $ denotes the fractional part, as adopted in the book Concrete Mathematics, but unfortunately this is not a "standard" notation as well.
$\endgroup$ $\begingroup$Many mathematicians consider the$\bmod$symbol not as an operation, but as a way to indicate a relation between two numbers. That is, it makes sense to say $$\color{green}{a\equiv b\pmod{n}},$$ meaning that $a-b$ is a multiple of $n$, but it doesn’t make sense to say $$\color{red}{a\bmod n=b\bmod n},$$ since the symbol doesn’t mean anything on its own. Of course, this isn’t the opinion of everyone, and you’ll very probably be understood if you use this notation, but I’d recommend against it.
Instead, you might define a function for the remainder in your text, and use that. I’ve seen some mathematicians use $$\color{blue}{r_n(a)},$$ for example, but you could use any other similar notation, as long as it’s understandable, and looks good (which arguably isn’t true when using the $a\%b$ notation). Furthermore, in your definition, you can specify what happens in the edge cases, if needed. What is the remainder of a negative number? What about a non-integer? Whatever you want to do in these kinds of cases will depend on your interpretation of what a remainder is, which could not necessarily correspond to the normal usage of the$\bmod$notation.
$\endgroup$
