Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
3  
You can always do $A - (\lfloor A \div B\rfloor \times B)$ –  Christopher Liu Dec 21 '13 at 17:00
6  
You can write the remainder as $\ A{\rm\ mod\ }B.$ –  Bill Dubuque Dec 21 '13 at 17:01
5  
"mod" is pretty standard. –  vadim123 Dec 21 '13 at 17:03
2  
@ApprenticeHacker Ok, I will post an answer. –  Bill Dubuque Dec 21 '13 at 17:10
1  
Wasn't sure if I should write this as an answer or not. There is a problem in that the mod operation in programming is defined in terms of the division algorithm being used. Specifically there is floored, truncated, or Euclidean division. And mod provides different results for each choice. Writing the Euclidean algorithm using the modulo operator seems then circular to me. In other words: you can use the euclidean algorithm to define mod, but not the other way around. –  Tim Seguine Jan 10 at 11:59

4 Answers 4

up vote 13 down vote accepted

Per request, I post my comment(s) as an answer, and add some further remarks.

The notation $\rm\ a\ mod\ b\ $ denotes the remainder when dividing $\rm\,a\,$ by $\rm\,b\,$ using the division algorithm. The same notation is used in other domains that have an analogous (Euclidean) Division Algorithm, e.g. polynomials with coefficients over a field.

Also "mod" is also as a ternary relation (vs. binary operation) when dealing with congruence relations, e.g. $\rm\ a\equiv b\pmod n\iff n\mid a-b.$

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 canonical normal forms, or arbitrary equivalence classes. For example, imagine how inconvenient it would be to state the laws of fraction arithmetic if one required all fractions to be in normal (reduced) form, i.e. in lowest terms. Instead, it proves very flexible to work with arbitrary equivalent fractions, e.g. to choose both with a common denominator before adding fractions.

The use of the percent sign to denote mod (as in the C programming language) has not percolated to be standard in 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 "mod", since that notation is ubiquitous in mathematics. 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 simple fractional example mentioned above).

share|improve this answer
    
Needed to add, if you wish to use a\%b in LaTeX to denote the remainder, you should write a \mathbin{\%} b or better define it by \renewcommand*{\bmod}{\mathbin{\%}} and then it's a \bmod b. –  yo' Dec 21 '13 at 22:00
2  
The percent operator in 'C'-like languages is a remainder operator not a modulo operator. Why Kernighan and Ritchie made this decision is lost in the mists of time, but it is unfortunate. Here is an article on the difference by one of the world's C# experts: blogs.msdn.com/b/ericlippert/archive/2011/12/05/… –  Pieter Geerkens Dec 22 '13 at 1:13
    
@Pieter It is not clear to me what you mean by a "remainder operator vs. modulo operator". Above I distinguish between mod/remainder as an operation that yields a particular (canonical) choice of an equivalence class, vs. the use of mod as a ternary relation $a\equiv b \pmod R \iff (a,b)\in R.\,$ I do not address any choices having to do with implementation of the remainder operations (or the associated division algorithm). –  Bill Dubuque Dec 22 '13 at 16:50
    
@BillDubuque: The % operator in C-like languages does not respect the equivalence classes of a finite ring over the integers under normal multiplication and addition when one or more operands is negative. Forgive me if my terminology is not spot on - it has been almost 4 decades since I last did the algebra rigorously. –  Pieter Geerkens Dec 22 '13 at 16:54
    
@Pie Yes, that's incorrect terminology. The article points out that C's remainder operation results from rounding the quotient towards $0.$ So, because dividend = quotient * divisor + remainder this implies $-123 = -30 * 4 - 3,$ so here $\rm -123\ mod\ 4 = -3$ vs. $1$. So remainders mod $4$ are not canonical. They lie in the interval $(-3,3)$ vs. $(0,3)$ But they are in the same equivalence, class, e.g. $-3\equiv 1\pmod{4}$. Some languages have multiple division operations that round the quotient various ways e.g. floor,ceiling,truncate,round in Common Lisp. –  Bill Dubuque Dec 22 '13 at 17:40

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.

share|improve this answer
    
+1 thanks for the appendix mentioning the programming part. –  ApprenticeHacker Dec 21 '13 at 17:13
    
You're welcome. I saw I hadn't, at first, answered all of your question! ;-) –  amWhy Dec 21 '13 at 17:14
    
I think it may be a little dangerous to believe that "$A\mod B$" is understood to mean the remainder (not to mention the question about the normalization of the remainder. Better to explain it in the set-up, to avoid misunderstandings. –  paul garrett Dec 21 '13 at 22:12

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.

share|improve this answer
    
I think formally you select a canonical element from each congruence class and the mod operation maps an element to the canonical element of its congruence class. For some domains this might require the axiom of choice. –  Tim Seguine Dec 21 '13 at 20:19
    
@Tim: Unfortunately, in many computer languages the operator that's commonly referred to as the "mod" operator [often denoted as %] does not each equivalence class to a single canonical element, but will map all but one of the classes to two elements each. For example, in current dialects of C, C++, C#, and Java, even though 4≡1 (mod 3), and -5≡1 mod 3, 4%3 will yield 1 and (-5) mod 3 will yield -2. –  supercat Dec 22 '13 at 5:11
    
@supercat yeah, I am actually aware of that. And I think most often when mathematicians speak of the operation they talk about the canonical projection, and reserve modulo for referring to the equivalence relation. –  Tim Seguine Dec 22 '13 at 12:32

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 your normalizing the remainder: e.g. that you are insisting that it is an integer in the interval $[0, |B| - 1]$.

share|improve this answer
    
+1. How would I go about explaining the meaning of my notation though? Just a statement in english? Something like "Where A % B denotes the remainder when A is divided by B" ? –  ApprenticeHacker Dec 21 '13 at 17:25
3  
@ApprenticeHacker: I think that should be fine in most contexts -- assuming you say how you're normalizing the remainder. There are actual several choices: e.g. you might pick the representative with smallest absolute value: $5\% 3 = -1$. Or you might pick the remainder to have the same sign as the as the first argument but still smaller in magnitude than the second: $-5 \% 3 = -2$. Or you might choose it to have the same sign as the second argument: $-5 \% 3 = 1$ but $5 \% -3 = -1$. –  Hurkyl Dec 21 '13 at 17:27
    
+1, in particular for it's undesirable. I completely agree. –  egreg Dec 21 '13 at 18:09
    
+1 for noting that % is a remainder operator in C-like languages, and not a modulo operator. –  Pieter Geerkens Dec 22 '13 at 1:14

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.