Talk:Modular arithmetic/Archive 1

Apology

I'm sorry. I didn't look good enough to find this topic. --Georg Muntingh

Congruency symbols

I can't see the congruent symbols (IE 5 on Win2000). --Jeff 20:55 Oct 25, 2002 (UTC)

Same.

Mozilla/5.0 (X11; U; Linux i686; en-US; rv:1.5) Gecko/20031107 Galeon/1.3.10 (Debian package 1.3.10-3)

--Andrew "Netsnipe" Lau

Notation

The notation ≡ is much more common when referring to elements, although "equals" is not incorrect. As for the subscript notation, I very much dislike this notation, esp. when a prime modulus is used, for the reason that this notation is also used to denote localisation at the prime ideal (p), which is completely different from factoring out by the ideal. I took out the comments on the origin of the term "ring", because I don't think that's the origin -- for one thing, not all rings are finite or have cyclic group structure. I've heard two more convincing theories that ring simply means "collection" and that Hilbert used "ring" because, in essence, number fields are finite extensions (i.e. sufficiently large powers of integers are linear combinations of smaller powers). The beginning stuff about computer notation and use seems a bit out of place from the mathematical discussion. Revolver

Clock arithmetic

Hey math folks, just writing to have one or more of you verify the accuracy of my statement:

"However, unlike clock faces, numbers in modular arithmetic usually start with 0, thus musical set theory uses mod12: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11; to represent 12-tone equal temperament."

From Clock arithmetic, and to ask if this should be stated somewhere in this article. Hyacinth 02:49, 7 May 2004 (UTC)

I'm not sure what you mean, really. "Numbers in mod arithmetic start with 0", you can list a set of reps in any order you want. If you're thinking of the entire set as the orbit of a group action, you can start with any element, 7, 8, ...11, 0, 1, 2, ..., 6. So, my guess is the way you're thinking of it, it's not really accurate. Revolver 03:09, 5 Jun 2004 (UTC)

Modulo in computer science

Most of the content resulting from the following discussion now lives in a separate article, Modulo operation.

Today I gutted the erroneous formulas that were in the implementation section. Apparently, no one had tried to use them. I also removed an assertion that the modulus is a remainder that would always be non-negative. The definition of remainder when dealing with a negative divisor or dividend is not entirely clear to me, based on how modulus functions operate in programming languages. On Talk:Remainder, I have requested some clarification. Based on the way the formulas I updated were written, it's apparent that I am not the only one who is having trouble with the broad definitions given. - mjb 05:31, 12 Jul 2004 (UTC)

I am not a computer science person, but I actually feel the original definition was better. It clearly stated that the codomain (target) set of the computer mod function was {0, 1, ..., n-1}. The way it is stated now is ambiguous and unclear. I have no idea what "ordinary division and remainder" mean. Furthermore, I don't see how the negative number case requires any special comments. If you use the definition originally given (essentially, a projection onto a specific set of representatives), then there's really nothing new to say. If people don't know how to calculate a remainder so that it lies in {0, 1, ..., n-1}, that is something that should be addressed on one the pages dealing with basic arithmetic, not here. Revolver 07:19, 12 Jul 2004 (UTC)

Thanks for the feedback. I came here to find an explanation of the modulo operator / function in programming languages, because my own experimentation with negative numbers (be they integers or not) as the operands / arguments was not, uh, congruous with my previous understanding of modulo.

Well, this is an issue for computer scientists or programmers to decide, it's not really about mathematics. Programmers are free to define (program) the "mod" function however they want. Revolver

I found the article to be somewhat helpful in increasing my understanding of modulus as being part of this larger concept of modular arithmetic that I previously knew nothing about, but it did nothing to help me understand why my computer tells me 7 mod -3 = -2 rather than -1, which would seem to me to be the one and only "remainder" after dividing 7 by -3.

7 mod -3 = -2 because 7 = (-3)(-3) + (-2). To see it another way, 7 is congruent to -2 mod -3, (since 7 - (-2) = 9 is divisible by -3) but not congruent to -1 (since 7 - (-1) = 8 is not divisible by -3). Revolver

Similarly, I didn't see why -7 mod 3 = 2, or why -5.25 mod 1 = 0.75 rather than -0.25.

Same reasons. -7 = 3(-3) + 2. As for -5.25 mod 1 = 0.75, rather than -0.25, again, this is precisely what I was talking about earlier, it depends what choice of representatives you use. You get 0.75 from -5.25 = 1(-6) + 0.75, and you get -0.25 from -5.25 = 1(-5) + (-0.25). In a certain sense, both answers are "correct". In another sense, you really should choose one at the beginning fixed, so that "mod" is a well-defined (correctly defined) function. Revolver

As for the {0, 1, ..., n-1} statement, it seemed to be asserting that the evaluation of a mod n should/will always result in a non-negative integer.

If you define it that way. The point is, you don't have to define it that way! There is no single "mod" function out there that is the "correct" function, or possesses what we "really mean" by "mod". There's an infinite number of possible functions. You just have to choose one. This is up to whoever is doing it. In this case, it would be up to the individual programmer. There may be a standard convention in computer science; I don't know, I'm not a programmer or computer scientist. I do know that it is certainly possible to choose different sets of representatives (different "mod" functions) and program them differently. This is possible on mathematical software (maple, mathematica, mupad), e.g. So, to answer you question, if you define it that way, yes it will give you a nonnegative integer. If you define it another way, it might not. Whether it should be defined that way, is a subjective decision taken by the programmer (or mathematician, in the case of calculations or proofs).Revolver

I didn't see this as an instruction to make the the remainder of a ÷ b fit into that set somehow, which AFAIK could only happen if a and b were restricted to the set of non-negative integers; rather I saw it as an assertion about the range of values that the remainder would have for all a and b regardless of what they are.

No, that's not correct, exactly. It was just the first thing you said -- an instruction to make the remainder fall in a certain set, not an observation or a property inherent in every "mod" function, which is the last claim you make. It's not a claim about a property of a function, it's a definition of a function. Revolver

Since this assertion contradicts what I find in actual practice, something here needs to change. You seem to feel otherwise?

There's no contradiction. People have defined different "mod" functions in practice, and you're comparing them and feel uncomfortable that they don't agree. But it's the same situation as declaring f(x) = sqrt(x) > 0, and g(x) = sqrt(x) < 0 for x > 0, and then complaining that 2 = f(4) = g(4) = -2 is a contradiction. There's no contradiction, f and g are simply different functions. Revolver

I excised as little of the article as I could in order to justify the results of my experiments,

Again, there are no "experiments" to be made. Playing around with your calculator will only tell you how your specific calculator has been programmed, but it doesn't tell you properties of some universal "mod" function, because there's an infinite number of choices. This issue is a matter of definition, not of emperical observation. Revolver

and added what little bit that seemed to be necessary in order to prevent the definition (that modulo = remainder after division) from being misinterpreted, and I also offered an implementation formula that "works" for me.

You mean, works for your calculator. If I program differently, it won't work for me. Revolver

I did not attempt to explain why the computing version does not jive with the older convention. I can't explain, which is why I'm asking for help.

It's not that it doesn't jive. In fact, it jives perfectly. In both math and programming, you have complete freedom in defining your function, as long as you pick n-1 integers such that every integer is congruent to exactly one. Revolver

Now, you seem to be saying that you don't know what "ordinary division" is. I am talking about all these statements and implications that "-7 mod 3" = "the remainder after dividing -7 by 3". Perhaps in school I was not exposed to certain nuances of basic division, but I wouldn't think that -7 divided by 3 would be anything other than either -2.33333(etc.) or the quotient -2 with a remainder that is the difference between -7 and (2)(-3). This is ordinary division to me.

I wasn't referring to the division in the rational numbers, of course I know what that is. I meant, I didn't know what "ordinary division" meant in terms of the division algorithm for the integers, how you choose your quotient and remainder, given there's an infinite number of choices. Revolver

The fact that these assumptions about remainders are apparently bad in the contexts of modulo in computing and modular arithmetic in general leads me to believe that there is some extraordinary form of division / remainder-determination that I'm unaware of. - mjb 11:57, 12 Jul 2004 (UTC)

"mod(x,y) = x − y × floor(x ÷ y)"

This formula does not give the correct answer for negative numbers. For example, 1 mod -2 is 1 - (-2)(floor(-1/2)) = 1 + 2(-1) = 1 - 2 = -1, not 1. Revolver 07:26, 12 Jul 2004 (UTC)

In the context of programming languages, the formula seems to be entirely correct (well, for the one I tried, Python, and also based on what I saw in the Perl implementation link at the end of the article). For example, in the Python command interpreter, I get the same result from my function as I do with the built-in % operator and the equivalent built-in method on the numeric types. mjb 11:57, 12 Jul 2004 (UTC)

I'm sure you do. That's not my point. My point is, the function is inconsistent with the choice of the set of remainders {0, 1, ..., n-1} originally made. I assume this is the remainders you want for nonnegative integers, I'm just saying if you put negatives in, you don't stay in that set. Now, what this means is that your function (and apparently, your computer's function) use different sets of remainders based upon whether the input numbers are negative or not. This is okay, if that's what's people want. Personally, I think it's inconsistent and confusing, but in the end it's subjective. Revolver

>>> from math import floor
>>> def mod(x,y):
...   return x - y * floor(x / y)
...
>>> mod(1.0, -2.0)
-1.0
>>> 1.0 % -2.0
-1.0
>>> a = 1.0
>>> b = -2.0
>>> a.__mod__(b)
-1.0

Okay, it depends what you mean, the confusion arises because you didn't specify exactly what the set of representatives was; in this case, if you stay with the definition originally given, you see that it breaks down for negative moduli. This doesn't mean the definition is wrong, it just means the definition doesn't make sense for negative moduli. All you have to do is say, "for negative moduli, let the set of reps be {0, 1, ..., abs(n) - 1}, where abs(n) is absolute value of n." But, you could define it differently. Just because a definition doesn't make sense for particular cases doesn't mean the def is flawed, you just have to expand the def. Revolver 07:40, 12 Jul 2004 (UTC)

If the definition makes no sense for (infinity ÷ 3) use-cases, constrains the set of results to something other than what it should be,

"Should be"?? Pretty subjective phrase. For you, it obviously "should be" defined for all integers. For the function itself, it's perfectly happy to live in the nonnegative integers, so from it's point of view, nothing is wrong. Revolver

and clearly needs to be expanded, how is it not "flawed"?

It's not flawed, because given its domain, it's a well-defined (unambiguously defined) function. Here's an analogy. Define f(x) = sqrt(x) for x > 0 or x = 0. This is the standard square root function defined on the nonnegative reals. Now, is there something wrong with this function? From the function's standpoint, the answer is no. It's defined unambiguously on its domain. Of course, we might think it "should be" defined for negative numbers. Then we develop the arithmetic of complex numbers and define it on all the reals in some fashion. (Note, there is a choice here as well!) Does this extension of the square root function to all of the reals mean that the original function defined only on the nonnegative reals was "flawed" in some way? No. (Well, it does if you want to take square roots of negative numbers!) The point is, the viewpoint that a rigorously defined function is "flawed" is subjective. The original definition that didn't work for negative moduli is "flawed" in the sense that the domain is smaller than we want it to be. So, yes, I guess it is flawed. But that's a subjective decision, not a mathematical truth. Revolver

Regardless, please feel free to add back in whatever is missing or clarify whatever is ambiguous. I just don't think you should assume that "basic arithmetic" explains the behavior of modulo in computing, or that the statements in the previous version of the article were sufficient. If an understanding of representatives and projections(?), which doesn't sound like basic arithmetic to me, is required in order to properly interpret a simple definition like "the remainder after division", then please say something to this effect and link to the appropriate articles where I can read up on it. - mjb 11:57, 12 Jul 2004 (UTC)

Maybe so. It's possible to understand what's going on here without talking about representatives and projections. All it means is, keep adding or subtracting multiples of the moduli (second number) until you get a number that's an accepted "remainder". If you get -8 mod 5, and -8 isn't an accepted remainder, but 2 is, then add 10 = 5(2) to it, and get 2. That's all, you can just keep adding or subtracting these multiples into you get a remainder you want. That's what I meant by "explaining in terms of basic arithmetic". A full discussion of mod functions and how to choose, implement them, etc. i.e. an explanation from a programmer's or computer scientist's point of view will have to refer back to the mathematical discussion and talk about sets of representations in some way. Revolver 00:45, 13 Jul 2004 (UTC)

Some math articles that (hopefully) might be helpful on modular arithmetic and above discussion:

• equivalence relation
• equivalence class
• partition of a set
• division algorithm (This one needs some work and has some errors, to say the least...I find it amazing how we have dozens of fleshed out, well-written articles on homotopy theory or category theory, but it took until a couple days ago before "division algorithm" was even created???)

Revolver 01:08, 13 Jul 2004 (UTC)

Revolver- Your last set of comments was quite helpful. Indeed, the problem was in that I didn't understand the nuances of division with remainders. I mistakenly believed that there was only one correct quotient and remainder, and that the statement about the remainder set was intended to inform, not constrain. Once I understood that the quotient / remainder combination in any division problem was, without constraints, an infinite set, the rest fell into place; it is clear to me now that a modulo function or operator must take into account not only the divisor and dividend, but also a desirable remainder set.

I suppose I do agree that explaining these topics is beyond the scope of this article, but given that the level of understanding that I had coming into this really isn't that uncommon, I think it would be good to at least allude to them explicitly. For example, one could say "because the division algorithm potentially produces an infinite set of remainders, the modulo function in computing can only be meaningful if the remainder set is constrained. It is typical to constrain it to (whatever) for a ≥ 0 and n > 0, (whatever) for a < 0 and n > 0," and so on.

Anyway, thank you for being patient. Also, you might want to consider toning down the emphasis (bolding) a bit; I initially interpreted your end of the discussion as being unnecessarily hostile. - mjb 07:08, 14 Jul 2004 (UTC)

Thanks, I'll take that into account. I forget that italics and boldface come across visually stronger than intended sometimes. I probably use them too often, when I'm just trying to give what would be a slight verbal emphasis (if I were talking). I also tend to pitch my "talking" at too high level at some of these articles that are on more basic topics, or read by a variety of people who may not know certain terms or ideas. This is not really personal, as much as the fact that most of the math articles I work on are at a certain level, and you just get used to that level if that's most of what you write on. Also, having just graduated after several years in grad school, I'm ashamed to admit that most of the people I've been around (IRL!) the past several years are math people. (Something to take care of now!) So, it's really more habit and assumption, not personal. Revolver 08:00, 14 Jul 2004 (UTC)

If people don't know how to calculate a remainder so that it lies in {0, 1, ..., n-1}, that is something that should be addressed on one the pages dealing with basic arithmetic, not here.

I can see how this could really sound hostile. I wasn't meaning to say that an explanation on what a "mod" function is, or an explanation about choosing a set of remainders was something in "basic arithmetic" that didn't belong here. Those are conceptual things that I wouldn't call "basic arithmetic". I was actually referring to the process of finding the right remainder from a set, given that you have that set and that you understand what a set of remainders means, i.e. actually just adding or subtracting multiples of the modulus (like I did above) until you find a remainder. That I do think is more with arithmetic, and that's what I meant about "should be addressed..." Revolver 08:08, 14 Jul 2004 (UTC)

---

As of tonight, in response to the discussion above,

1. I removed the examples with negative operands, so as not to insult the mathematicians who consider them redundant;
2. I reinstated the explicit constraint on the remainder set, expressing it in a manner that I think will be understood by users of programming languages. I wanted to include a pointer to the division algorithm/theorem article, but couldn't work it into the text cleanly.
3. I inserted some text that should sufficiently qualify the implementation algorithm observed in Perl and Python.
4. I renamed the section heading from "Implementation of the 'mod' function" to "Implementation of modulo in computing", and changed it from a level 2 heading to level 3. It's possible that it should even be level 4.
5. I changed the examples in the implementation section to use a and n rather than x and y, in keeping with the convention from the preceding section.

I believe that in combination, all of the additions are likely to drive the point home that modulo implementations in computing may vary, a situation that is to be expected due to the nature of division and modular arithmetic. This should serve to mitigate the default assumption that such variations are the result of inadequate specification, as is often the case in computing applications.

I'm still not entirely happy with how it all reads, but I think it's better than it was. - mjb 04:44, 16 Jul 2004 (UTC)

---

Okay, a few remarks:

'Old' convention and 'New' convention? The computer-one does not conflict with the mathematical one, and the mathematical one is certainly still used, it's even the _base_ for the computer-one. In fact, the mathematical one is what modulo _is_, while the Computer Science thingy is an additional convention used to make programming with modulo possible.

What the original writer probably meant, is that instead of in Mathematics, where multiple 'answers' are correct (equal) modulo 'n', the result of the the '%' or 'mod()' operation in programming languages has been well-defined: it will not give you a random answer that's correct, but rather you could calculate what the answer is. Yes, that tends to be for most cases the same as the remainder of integer division, but that definition is vague at best, and 'remainder' isn't so well defined.

The fact is, different programming languages have defined '%' or 'mod()' differently. Some define m = a mod n as "the integer m that is congruent modulo n to a, and falls in the range 0 <= m < |n| (I)". Others let the answer be in the range -|n| < m <= 0 (II) for negative a (java is such an example, -5%3 equals -2 there), and yet again others define the answer to be in (II) if and only if n is negative, regardless of the sign of a. (note that the current article uses 0 < |r| < |n|, which is not only ambigious, but also obviously wrong, as now r cannot be a multiple of n, ergo there is no r in this range such that r = kn mod n for any integer k)

--Jeroen van Wolffelaar <jeroen@wolffelaar.nl> (please do sent me a mail upon update, I don't have the time to monitor this page) Maths & CS student at Utrecht Unversity, NL.

You are mistaken to say that the mathematical usage is not well defined. You are also mistaken about what I "probably" meant. To say that 73 is congruent modulo 5 to 98 is perfectly well defined. Michael Hardy 01:07, 22 Nov 2004 (UTC)

I did not say that the Mathematical usage is not well defined, it is. Well, common Mathematics have _defined_ what modulo is, it isn't a mere convention. What I meant with well-definedness in my second paragraph, is that the % or mod() operator is well defined, something completely different! In Mathematics, there are infinite integers that

No -- there are not "infinite integers"; there are infinitely many integers; each one of those is finite! Michael Hardy 22:19, 4 Dec 2004 (UTC)

are equal to a given other number modulo a given 'n',

No; they are not equal to the others; they are congruent to the others. One writes "a ≡ b", not "a = b". That's why they're called "congruence classes". Michael Hardy 22:19, 4 Dec 2004 (UTC)

the congrulence classes are of infinite size. A % or mod() operator however, in Computer Science, needs to have one well-defined result to be useful.

The well-defined result in the math convention is the truth-value "true" or "false". In the case of "(63 ≡ 78) mod 5" it is "true"; in the case of "(63 ≡ 79) mod 5" it is "false". So it is not true that "multiple answers are correct"; the question being asked is not "what number is ...?", but "are these two numbers congruent or not?" Michael Hardy 22:19, 4 Dec 2004 (UTC)

Every programming language has this operator well defined, but not all in the same way. The two prevailing uses have each their own advantages. The java way has the so-called Euclidian property: a == (a/b)*b + a % b always holds for every integer a and b (this is a way of defining remainder by the way). Because in programming with integer devision one rounds towards zero, a negate left-operand of % must yield a non-positive modulus.

The C way does not have this Euclidian property, but on the other hand, for positive n, a%n will always be in {0, 1, .., n-1}, making programming for example hashtables easier. Also, a%n == b%n if and only if a and b are congrulent modulo n. This property does not hold in Java!

Note that I do not in any way want to attack the original author, but I do think a few details need to be worked out.

--Jeroen, Mon Nov 22 01:40:02 UTC 2004 (mail on any addition to this discussion again appreciated)

Your remarks above seem to imply that the article denies that the computing convention evolved from the math convention. It's not stated explicitly, but only because it seemed obvious. Anyway, I'm having a hard time being sure exactly what you think needs to be altered in this article. Michael Hardy 22:19, 4 Dec 2004 (UTC)

I believe (I have corrected what I think is an obvious typo above) that there is the thing that Java does, when the modulus is negative, which is an unobvious thing to do from the mathematical point of view; and this shows that what we mathematicians think of as the 'normal form' of remainder is not quite the only way to think about it. Charles Matthews 22:30, 4 Dec 2004 (UTC)

Usage in check digits

I'm not sure whether it should be under modulo or modular arithmetic, but its use in calculating check digits is important and should be mentioned in whichever article[s] it is appropriate for. –radiojon 01:58, 2004 Jul 31 (UTC)

Definitely it should be in modular arithmetic and NOT in modulo. Michael Hardy 00:23, 1 Aug 2004 (UTC)

More modulo in computing

I cut the following passage from the section The newer convention, used in computing in the main article. Comments like this belong here on the talk page (that's what its for).

The paragraph above must be corrected, this is not giving a normal form. A normal form would imply a unique representation of equal residue classes. Mathematically spoken, the result of the modulo operation is a representative for its residue class, and it should be independent from the choice of the generator of the ideal. But for the definition above, a mod n depends on the sign of n, but n and −n are generating the very same ideal, so that a mod n and a mod (−n) should give the same representative as result.

This "newer convention", used even in some language proposals like the one for JavaScript 2.0, is therefore totally unsufficient from a mathematically point of view, but there are two adequate conventions used by mathematicians over long times. The most used of them, and therefore the canonical choice for representatives is to place them in the range from 0 to n − 1.

It would be wise to check a definition like this using GAP, an algebra programming language written under the critical views of algebraists:

gap> −1 mod 4; ... result: 3

gap> −1 mod −4; ... result: 3

So as not to be out of context, "The paragraph above..." refers to

According to the newer convention, in general, a mod n is the remainder on integer division of a by n. Depending on the implementation, the remainder r is typically constrained to 0 < |r| < |n|, with a negative remainder only resulting when n < 0.

The difference in conventions is not very serious, in fact; it is reasonably thought of as reflecting the preference, for computational purposes, of a normal form over the underlying equivalence relation. This can be regarded mainly as a notational convention in this case, where there is a strict-sense normal form.

-- Fropuff 05:58, 2004 Oct 20 (UTC)

Replying to User:Michael Hardy

Michael Hardy wrote: The recent edits here are very unfortunate. The same person who was so adamant that modular arithmetic is ONLY arithmetic of congruence classes has now put in this first sentence that contradicts that.

Dear Michael, you are right. The page the way it is, is a reverted copy of how it was in 2002. I think the purpose of the very first sentence is to intuitively introduce modular arithmetic. I am looking forward to any suggestions to improving this page. Thank you. Oleg Alexandrov 01:20, 9 Jan 2005 (UTC)