Talk:Modular arithmetic

From Wikipedia, the free encyclopedia
Jump to: navigation, search
WikiProject Mathematics (Rated B-class, Top-importance)
WikiProject Mathematics
This article is within the scope of WikiProject Mathematics, a collaborative effort to improve the coverage of Mathematics on Wikipedia. If you would like to participate, please visit the project page, where you can join the discussion and see a list of open tasks.
Mathematics rating:
B Class
Top Importance
 Field: Basics
One of the 500 most frequently viewed mathematics articles.

Old Talk Archives:

Notation[edit]

Dear Linas, what does (a+b)_n=a_n+b_n mean? This notation is not defined in the article. Do you mean:

[a+b]_n=[a]_n+[b]_n?

Thank you. Oleg Alexandrov 01:31, 9 Jan 2005 (UTC)

The article[edit]

I think this article has now very clearly lost its way. Time for a thorough edit, with abstract algebra given its due (and not made too prominent, as now is). The servers are currently having a hard time, but I intend to return and re-order the material. It must be done so as to make sense to first-time users of modular arithmetic. Charles Matthews 14:23, 13 Jan 2005 (UTC)

I'm sure it needs improvement, but as a person trying to teach myself on the net, this page comes near the point where one doesn't have to continue clicking deeper into a topic to reach the intuitive level after which they can use the back button for a change. Perhaps mathematical pages on WP could be given a little icon indicating the intuition score, perhaps a way to vote on this, and a link to a page where topics are organized on some kind of structure like a tree of mathematical knowledge and someone such as myself can start there and build from the ground up, or not so far from it. Simplistic idea? Probably. — Preceding unsigned comment added by 97.81.29.81 (talk) 04:25, 14 October 2012 (UTC)


I have reverted a change, to keep 'clock arithmetic'; the introduction is not solely for the benefit of mathematicians. Charles Matthews 15:56, 20 Jan 2005 (UTC)

I have 2 problems with this: first, the article makes it sound like "clock arithmetic" is just a synonym for "modular arithmetic", i.e. that its use as a technical term is on the same level. If you want to point out the term "clock arithmetic" as a colloquialism, fine. But, the way it's worded now, the 2 terms are given almost equal footing. Also, "clock arithmetic" seems to imply modulus 12. Revolver 4 July 2005 23:25 (UTC)

Invitation to a discussion about the future of modulo and modular arithmetic[edit]

The modular arithmetic page started in the early days of 2001, by AxelBoldt. It was a neat page about the ring Z/nZ. Now, many things can be said about modulo, and modular arithmetic. And people did say it. To such extent, that the pages modulo and modulo arithmetic became (in my opinion) very bloated, filled with all kinds of things, overlapping material, and plain mistakes. There was even an application section of modular arithmetic, inserted before the definition of modular arithmetic was complete. I myself found the modulo page (and from there the modular arithmetic page) when it was listed on the Wikipedia:Pages needing attention/Mathematics page.

Well, I tried to to some cleanup, after a while gave up, and just reverted to an earlier version, made modulo a disambiguation page, and split most of the material in articles originating from there.

Now, the modular arithemtic page did not stay clean for long, and started getting a very abstract algebra bent. And recently, the applications started creeping in again. All these are not bad by themselves (I love applications, I am in applied math), but the article is losing focus again. And I also realized that restricting "modular arithmetic" to only the ring thing is maybe narrow minded, and maybe better ways can be devised.

So, I would like to ask you to read the modulo page, all the pages which go from there, and I am looking for suggestions about what to do.

Oleg Alexandrov 19:31, 17 Jan 2005 (UTC)

Hello. Sorry to be seeming to ignore your various comments on my talk page. I think at some point I'll return to the modular arithmetic article. I do think some mention should be made of the fact that the conventions used in computer science differ from those used by mathematicians. Michael Hardy 19:29, 20 Jan 2005 (UTC)

When I was writing those comments, each one had a specific purpose in mind, but now if I look at it, it does look as if I am pestering you. If you thought so, sorry for that.
I am not on principle against establishing a connection between computer science and math as far as the modulo thing is concerned. I would think the last attempt was not very sucessful (I could mention more things that what is above), but we can try. I wonder if you could explain more about the "convention" thing, I still think this is too big a word in this particular setting.
Looking forward to a friendly conversation. Oleg Alexandrov | talk 20:00, 20 Jan 2005 (UTC)


For people new here, this is the "convention" thing we mean:

Definition of modulo

Two discrepant conventions prevail:

  • the one originally introduced by Gauss two centuries ago, still used by mathematicians, and suitable for theoretical mathematics, and (here, modular arithmetic is meant)
  • a newer one adhered to by computer scientists and perhaps more suitable for computing.

(here the mod operation is meant, that is the remainder)

A third sort of usage by mathematicians ultimately evolved from those, but may seem quite different. It is explained in the article titled modulo. (here, I think the jargon use is meant) Oleg Alexandrov | talk 21:15, 20 Jan 2005 (UTC)

We should revert to a much earlier version![edit]

Alexander Guy's recent edit missed the point in a way that I predicted a long time ago. I put at the beginning of this article a definition of "mod" that said there are two conventions: the one used by mathematicians since the beginning of the 19th century, and the one used in computer science. If we had kept that, he wouldn't have missed the point. It looks as if he wanted to parse the sentence as

a = (b mod c)

rather than as

(a is congruent to b) mod c.

And the use of "=" in this context is very bad, since people may think it means "equals", and it does not. Michael Hardy 03:20, 19 May 2005 (UTC)

What you should do Michael, is be more talkative. You are quite good at stating your point then closing your eyes and ears to other poeple's plea for discussion (see above). So, are you willing to put your foot in the water this time? Oleg Alexandrov 05:58, 19 May 2005 (UTC)
I am talking to myself here, but probably a paragraph or two about the various uses of modulo is in order (on the modulo page). The information in the current modulo disambiguation page seems kind of little.
I replaced everywhere the equal sign with the correct symbol ≡. This symbol should display in any browser having at least rudimentary Unicode support. This, and the note I put on top should probably be enough of a hint to computer scientists that this is not your computer's mod function. Oleg Alexandrov 01:30, 21 May 2005 (UTC)
I'll be joining you here shortly ..... Michael Hardy 03:28, 21 May 2005 (UTC)

Guilty As Charged[edit]

I was staring at, and it didn't click in my head to look above. I found it confusing, but maybe I've just been programming for too long. Thanks. Alexander Guy 03:54, 19 May 2005 (UTC)

Merging back?[edit]

It was agreed by the recent contributors to this article that two articles need to exist. One more elementary, for the general public, which will be modular arithmetic, and another new one, called modular arithmetic theory with more advanced things and uses in modern mathematics. This parallels graph and graph theory.

This modular arithmetic article needs more things about its connections with other areas of knowledge, like computer science, as User:Michael Hardy remarked. Still to be discussed and done. Oleg Alexandrov | talk 21:19, 29 Jan 2005 (UTC)

I fail to see the need for two separate articles. By reading the two articles, they seem to talk about the same concept, namely modular arithmetic. I agree that not every layman knows the use of modular arithmetic in ring theory, for example, but in wikipedia we don't remove the discussion because it is for advanced readers. I added a merger tag. -- Taku July 5, 2005 01:50 (UTC)

I disagree with merging. As the name says, modular arithmetic is about adding/multiplying numbers modulo something. This is not the same as taking the remainder which modulo operation is about. It is not the same as the informal usage discussed in modulo (jargon). I of course agree that these words have common origin, and maybe it should be elaborated on that. But modular arithmetic is not the place for that. That should go in modulo. Oleg Alexandrov 5 July 2005 02:08 (UTC)

So are you saying addition and multiplication is arithmetic, while finding the remainder is not? Also, I have never heard that modular arithmetic is about math and modular operation is for cs. If the name modular arithmetic has to be reserved for the usage in algebra, we can rename the article so it can contain the general idea. By skiming the above discussion, I can see there is a subtle difference (like cases of negaive integers or calculating the remainder of an real number in cs sense). But I don't think readers would appricate that subtlety. Giving a precise definition and limiting the article to it are two different things. -- Taku July 5, 2005 02:30 (UTC)
Right. But giving a precise definition and merging all that stuff back in here are two different things also. :) This artice was in a very bad shape when all the stuff was here, in particular the computer science usage was inserted in the middle of the math usage, so the math usage was both above and below. You are welcome to expand a bit on the computer science usage, but I myself would not be happy with all those article crammed back in here. Oleg Alexandrov 5 July 2005 02:40 (UTC)
Well, cleaning up the bad stuff and separting it off are two different things as well :) I will try if I can have a good article (or at least start). Make corrections, comments or reversion after that. -- Taku July 5, 2005 03:17 (UTC)
Maybe you should wait a bit to see what others have to say. Oleg Alexandrov. Comments welcome. Oleg Alexandrov 5 July 2005 03:40 (UTC)
Right. So far I merged modular and modulo into one article called modulus and modulo. I am thinking of expanding that article more so as to make it a non-disambig page to clarify terminology. I think that's a good start. What do you think? -- Taku July 5, 2005 03:50 (UTC)

Good. I might agree with you that the computer term has something to do with modular arithmetic, but definitely not the jargon term. So I expect that one to not be here. Also, if you do plan to merge, maybe not all of modulo operation needs pasting here. We could still keep that one as a main article. Oleg Alexandrov 5 July 2005 04:44 (UTC)

Merging from advanced modular arithmetic theory[edit]

I don't agree with the merger. That article goes into too complicated math, and in my view, is not well-written. The link should be enough. What that article needs is a rewrite.

I would agree with that article to redirect here, without merging the information. Oleg Alexandrov 6 July 2005 02:50 (UTC)

Okay so what I'm hearing is: make that page into a redirect and set up links to the individual theorems for advanced topics here in this article. Is this correct?Guardian of Light 6 July 2005 13:12 (UTC)

I noticed this before, I think you should use the word "this" with more care. :) If you mean that advanced modular arithmetic theory be made to redirect here, with some links, then yes. If you mean that modular arithmetic be made into redirect to something else, then I don't agree. Oleg Alexandrov 6 July 2005 15:19 (UTC)
I do mean redirect advanced modular arithmetic theory here.

Guardian of Light 6 July 2005 19:01 (UTC)

Okay I merged them the best I could given the time constraints. If someone would look over it and see if there's anything amiss that would be great. I should be back on soon.

Guardian of Light 6 July 2005 19:24 (UTC)

I cut down on some of the advanced modular arithmetic theory stuff. I remember some of it from before, and I don't think it is well-written. Oleg Alexandrov 7 July 2005 02:06 (UTC)
Does that mean I can delete the temporary archive and be done with it?Guardian of Light 7 July 2005 16:42 (UTC)
I moved that one to an archive of the talk page, see the very top of this page. Oleg Alexandrov 7 July 2005 17:43 (UTC)

Pipe notation[edit]

An edit comment says (partial revert. I don't think introducing the pipe notation makes things more elementary or more clear. Also, there was a mistake. It is false that 24|12, rather, 12|24)

The error was introduced by a later anonymous person - thanks, anonymous error introducer! And it seems obviously wrong for the article not to contain the true definition of ab (mod n) which is the one that I gave. If you can find a way to restore that definition that would be good.

With deference to the long and fraught history this article seems to have, of course. If I'm just restarting a long-fought battle I'll drop it here. — ciphergoth 22:03, August 9, 2005 (UTC)

The comment was mine, obviously.
Glad to see it was the anon who put the error in. My point is the following. Here is how the definition of the congruence is now:
Two integers a, b are said to be congruent modulo n if their difference is divisible by n; that is to say, if they leave the same remainder when divided by n.
I guess is that what you would like, is to add to this sentence saying that notationally this is
n | (ab)
So, my point is that having the thing said in words is enough (their differences is divisible by n). I don't see what value putting new notation would introduce. I'd rather have people focus not on this pipe notation, but rather on the notation right after that, which is
38 ≡ 14 (mod 12)
What do you think? Oleg Alexandrov 22:17, 9 August 2005 (UTC)
Yes, that makes sense. However, it should reference divisor, not division (mathematics). Fixing now. — ciphergoth 07:28, August 10, 2005 (UTC)

Hello, I am writing here because the title says "notation". I think the mod-n-in-parentheses-at-right notation sucks as a notation because I couldn't understand what it meant when I first saw it, and the purpose of a notation and of symbols for communication is for people to understand each other. Thank you. I like the subscript-n-at-special-equals-sign notation better. — Preceding unsigned comment added by 62.38.153.70 (talkcontribs)

The mod n in parenthesis is the standard notation. "Pipe notation" (for divisibility) may or may not help. — Arthur Rubin (talk) 18:56, 26 June 2012 (UTC)

Algorithms[edit]

With deference once again to the fraught history of the page: I think the page has the balance of clock arithmetic, and the depth of mathematics just right now, but there's still the fraught question of "a mod b" as programming languages use it. The section on "algorithms" tries to cover this but does a terrible job. remainder does far better. I think we want to remove this section and replace it with a note that says 'a mod b' is sometimes used in computer languages to denote the related operation of finding the remainder of a divided by b. Then any discussions of the ways in which some languages (C but not Python) get it heinously wrong can go in remainder where it rightly lives. Sound good? — ciphergoth 07:33, August 10, 2005 (UTC)

A lot of that discussion about remainders in computing is in modulo operation. I agree with you that at least some words can be said about it in this article, then refer to modulo operation and remainder for details. Be bold! Oleg Alexandrov 15:13, 10 August 2005 (UTC)

Minor inaccuracy[edit]

I don't see any really good way around this, but the standard group of integers mod 12 is not quite the same as "clock arithmetic", which uses 12 instead of 0 to represent the class of multiples of 12. It doesn't affect the structure of the group though. Deco 18:10, 31 August 2005 (UTC)

I don't precisely agree. I'd say the "standard group of integers mod 12" refers to Z/12Z, and that has the equivalence classes themselves as members, not representative elements. Sure, if you're going to pick representatives, it's most usual to pick the numbers 0..11, but 1..12 is equally good. In any case, the mention of "clock arithmetic" is primarily meant as an informal introduction to the topic, and we pretty quickly get down to a precise formal statement which as far as I know is entirely accurate. — ciphergoth 18:37, August 31, 2005 (UTC)

DIV function[edit]

Why is there no article explaining the DIV function? There is no link from div and I feel that while Division algorithm contains related information it does not explain the programming function.

This page too should have a See Also link to div.

Syndicate 10:47, 23 October 2005 (UTC)

What is "DIV"? Do you mean the "remainder"? If so, see the section "Remainders" in modular arithmetic and the links therein. Oleg Alexandrov (talk) 12:22, 23 October 2005 (UTC)

What a nice article[edit]

What a nice tastefully written article this is. I think my decison a long while ago of splitting off modulo (jargon) and modulo operation was a good one. Oleg Alexandrov (talk) 20:28, 16 November 2005 (UTC)

My removals[edit]

I removed several paragraphs. Here is the explanation:

1. The sentence "Sometimes such b is called the residue of a (mod n)." is incoherent, as it is not clear to what it refers.

2. The common residue is defined below, where I think it is more appropriate. Mentioning that residue has nothing to do with residue in complex analysis is of little value, you could as well mention that it has nothing to do with residue in a pan after cooking.

3. I never heard of the modulus being called the "base". Anyway, I don't know what the value of that sentence is.

4. There were way too many technicalities about how to define the remainder. That issue is dealt with at remainder and modulo operation which are plentifully linked from above the text I cut and also one more time somewhere before that.

5. The part about "aserting" which I cut has been stated earlier, so this is a repetition. Oleg Alexandrov (talk) 23:14, 24 November 2005 (UTC)

Computer Science[edit]

The section on applications says:

"In computer science, modular arithmetic is often applied in operations involving binary numbers and other fixed-width, cyclic data structures. The modulo operation, as implemented in many programming languages and calculators, is an application of modular arithmetic that is often used in this context."

This is misleading. It is true that a mod operation is often used in programs and is present in most languages but this misses a very important point in that digital computers almost universally represent integers in a fixed number of bits which means that there is an implicit modulo operation after every arithmetic operation. Modulo arithmetic is in fact the very basis for computer maths. It is impossible for computers to not "appl[y] [it] in operations involving binary numbers and other fixed-width [...] structures". It might also be useful to mention this, and that it results from the fact that an AND operation of a number with (2**n)-1 gives the same result as modulo 2**n.

--67.65.21.209 19:59, 29 November 2005 (UTC)

I would agree with a very short description, with the bulk of stuff going to modulo operation, which is is the main article for that kind of thing (which should be manybe renamed modulo (computing). Oleg Alexandrov (talk) 20:29, 29 November 2005 (UTC)
It's true and interesting that there is an implicit reduction done after many operations, but the text you quote is more about constructions like "for(i=1;i<1000;i++) { if(i%2==0) { /* do something every other iteration */ }", and those are quite separate in my mind. In fact, I always knew about overflow, but it took me a few years before I became comfortable with using % as in the example above. Lunkwill 23:40, 29 November 2005 (UTC)

Lunkill, I see your point, but the words "operations involving binary numbers" really make it sound like you are talking about addition, subtraction, multiplication, etc. which are always modulo 2**wordsize unless they are implemented at a higher level, like an infinite precision library. For speed reasons (the avoidance of division and using storage for the result and remainder) your example is often written "if((i&1)==0)" due to the equivalence I mentioned before for powers of two. Also, it is sometimes just written with "if(i==1) i = 0; else i = 1; if(i) ..". It's still a "modulo" operation, but it may or may not require the use of a modulo operator. Maybe just change it to talk about data structures and not integers in that sentence and see my other response below for addressing arithmetic operations. Also, a specific examples for data structures would be ring-buffers and hash tables, if you are looking for something concrete. --67.65.21.209 09:07, 30 November 2005 (UTC)

Oleg, I agree that there is no need for much text on this topic as it is closely related to the dicussion of wrap-around. Maybe two small changes could address this: a) something like adding a sentence like "is utilized in the implementation of fixed width arithmetic operations in computer processors" in the application and b) if there is somewhere good to work a sentence or so about the relationship with the and operator that's great, otherwise it should be (I haven't checked) covered in modulo operation. --67.65.21.209 09:07, 30 November 2005 (UTC)

Fine with me, as long as you keep it short. :) And yes, reading modulo operation would be good too. Oleg Alexandrov (talk) 16:30, 30 November 2005 (UTC)
Looks like nothing was ever done with this. I'm the person who wrote the paragraph in question, and Lunkwill's interpretation of it is correct. I was saying that iteration over cyclic data structures is the most common application of modular artithmetic in programming. The part about "binary numbers" was in reference to bitwise operations, the other notable and common application of modular arithmetic in computing. I should have just linked to that article. I'll do that now. As for the modulo operation page, I think it should remain focused on the modulo operation, rather than trying to cover all modulo-in-computing topics. —mjb 23:44, 18 March 2006 (UTC)

Notation 2[edit]

Somewhere, I found notation "a ≡ b mod n" for "a ≡ b (mod n)". Is this a mistake or not? If is not mistake we should put it in, as alternative notation.--Čikić Dragan 12:46, 10 February 2006 (UTC)

Question[edit]

If you prove that a function F can take any value (mod 6) and can take any value (mod 12) and can take any value (mod 24) and so on, does that imply that it can take any value?--SurrealWarrior 20:11, 4 March 2006 (UTC)

no - consider f(x) = abs(x) + 3 — ciphergoth 11:17, 22 May 2006 (UTC)

Explanation of deletion of C++ code[edit]

Shortly after its addition today, I removed Jerrybtaylor's "modulo reciprical" [sic] C++ function because it is trivia (arcane trivia, at that) and is also not an example that helps explain any particular concept. —mjb 23:03, 18 March 2006 (UTC)

About definition of congruence relation[edit]

At our classes we did some problems which, in definition of congruence relation, instead integers a and b use real numbers. The meaning is that their difference remain integer. Such definition is wider than one used here.--Čikić Dragan 13:59, 19 May 2006 (UTC)

Rewrite Clock Analogy[edit]

I have rewritten the clock analogy at the introduction. The original paragraph was way too confusing, since 12-hour clock is not strictly modular arithmetic (the usage of 1 to 12 instead of 0 to 11). Therefore I changed it to the 24 hour clock system which is a better analogy. --changyang1230 04:36, 20 May 2006 (UTC)

I can't see the symbols in this page. It just appears as little squares. From the talk it is supposed to be the congruent sign? What about auto install font or something? What font it is?

It's Not an Analogy![edit]

Sorry Changyang, but IMO you have done this article a disservice. The clock dial is the basis and the origin of modular arithmetic. Your going "digital" has the effect of diminishing the subject and being misleading too. Please read up about the Gauss clock calculator, then you'll understand why a 12-hour clock is the perfect introduction to this article - and to modular arithmetic. Here's a quickie, [1]

Michaelmross 11:57, 8 February 2007 (UTC)

The clock dial was the origin?? I find that wildly implausible. What reason do you have to say such a thing? Michael Hardy 17:24, 11 September 2007 (UTC)

I think there should be a separate topic titled "Gauss Clock Calculator" with the history and importance of modular arithmetic - including its relation to Fermat's Little Theorem, Euler's proof of it, and its application in cryptography.

Michaelmross 18:29, 8 February 2007 (UTC)

Michael, I believe you wouldn't have described me "doing the article a disservice" if you read the version I edited on: http://en.wikipedia.org/w/index.php?title=Modular_arithmetic&diff=54143511&oldid=54033018

You might be right that the origin of modular arithmetic came from the clock dial, but that particular "clock analogy" paragraph never purported to demonstrate the origin of modular arithmetic. It was only meant to provide a good starting point for beginners who are new to the concept of modular arithmetic.

I changed the 12-hour clock to 24-hour clock because of the common term of "12 o'clock" instead of "0 o'clock", which is confusing when people are just beginning to learn this topic.

Wikipedia should serve as both a guide to beginner as well as a detailed resource for advanced users; but I believe it's best if we avoid confusion in the introductory paragraphs. --203.219.254.46 14:52, 11 September 2007 (UTC)

It was by me, changyang1230. --203.219.254.46 14:52, 11 September 2007 (UTC)


Someone needs to link "modulus" this this page.

(First post, be nice. Sorry if I double posted.)


67.121.121.199 23:24, 12 March 2007 (UTC)

Reduced residue class[edit]

I can't find any mention to a reduced residue class. Nor is there a distinction between absolute least and least positive representations. Peter Stalin 15:18, 27 March 2007 (UTC)

A whole new article could be devoted to residue classes. While this would deal with.....well, the actual arithmetic. I don't even see any mention to the division algorithm or such here.....Peter Stalin 18:04, 27 March 2007 (UTC)

Yeah, this is a big topic. The best thing to do is write many smaller articles, e.g., residue class, and then link to them from "see also" in here I'd think. Oleg Alexandrov (talk) 03:21, 28 March 2007 (UTC)
I just inserted material describing residue systems, as I have long felt that they should be described somewhere in Wikipedia. I originally had planned to write several new articles about them but much related material already exists in Modular arithmetic so I decided to include the definitions here as a new section and subsection and to create redirects from least residue system and complete residue system. Within this new material is a brief description of a reduced residue system and a link to the main article about that topic. — Anita5192 (talk) 23:52, 8 November 2011 (UTC)

Proofs of divisibility using modular arithmetic[edit]

I have seen elegant proofs of divisibility using modular arithmetic. Would this application fit in this article or elsewhere? Larry R. Holmgren 18:49, 1 May 2007 (UTC)

I would think so. Michael Hardy 01:06, 23 October 2007 (UTC)

More examples using 38[edit]

I came to see what MA was and was immediately struck with the question of why you chose 38 is congruent to 2 modulo 12, since you could also say that 38 is congruent to 2 modulo 18, was I missing something special about 12, etc. Would it be acceptable to add a sentence stating that there are other valid ways to write 38, but you arbitrarily chose 12 for the article? Or would that disrupt the flow? 65.220.25.66 14:24, 8 June 2007 (UTC)

Confusing[edit]

I found the intro paragraph a little confusing. I think it would be beneficial to show the work; rewording the first example: if my clock is 19:00 and I want to know what time it will be in 8 hours, the notation would be (19 + 8) mod 24, or 27 (mod 24), and the work I would do is 27 \div 24 = 1, with a remainder of 3, which would give me the time of 3:00. Yngvarr 12:55, 20 August 2007 (UTC)

Redirect from Boolean Arithmetic??[edit]

I'm really confused as to why "Boolean arithmetic" redirects here. After studying Karnaugh maps, logic gates, and boolean arithmetic today in my compsci class, I came to WP to sink it into my head a little firmer and find a completely unrelated topic being redirected to... why is this?

I'm assuming it's because there *is* no Boolean Arithmetic page, and somebody had the absurd notion that modulo was somehow related... at least it has "arithmetic" in the title. oo;

So, can anyone explain the reasoning on this??

Boolean Arithmetic: (A + B)' = A'B'

--69.225.132.158 07:39, 30 October 2007 (UTC)

The relationship is simple, although not entirely obvious: boolean arithmetic maps to arithmetic mod 2. Mathworld has a similar redirect. I think it deserves a separate article (or at least its own section) just to clarify how things are written using boolean notation. Dcoetzee 12:34, 30 October 2007 (UTC)

Conversion from congruence to equalivance[edit]

I think we should note the two differences and how to translate one from the other.

ab (mod n)

For some arbitrary constant whole number k: a = b + kn

Like the example with 38 ≡ 14 (mod 12): 38 = 14 + 12k 24 = 12k k = 2

--AllyUnion (talk) 21:44, 9 November 2007 (UTC)

modular inverse[edit]

modular inverse redirects here, but no occurence of "inverse" neither in this article, nor in the discussion, nor in "multiplicative group of integers mod n", and in finite field it isn't either. — MFH:Talk 20:17, 6 December 2007 (UTC)

RRS[edit]

In the line,

When n ≠ 0, has n elements, and can be written as:
\mathbb{Z}/n\mathbb{Z} = \left\{ \overline{0}_n, \overline{1}_n, \overline{2}_n,\ldots, \overline{n-1}_n \right\}.

I just want to mention that this has a name ("Reduced Residue System") for when this subject is introduced prior to group theory (whence it would be a ring instead, and a field when the modulus is prime, etc). So I would ammend the wording: "...and can be written as the reduced residue system: ..." but I don't want to interfere with your pedagogy here. Pete St.John (talk) 21:58, 28 February 2008 (UTC)

equivalence vs equality[edit]

In this line:

  • It follows that, while it is correct to say "38 ≡ 14 (mod 12)", "2 ≡ 14 (mod 12)" and "2 ≡ 14 (mod 12)", it is incorrect to say "38 = 14 (mod 12)" (with "=" rather than "≡")

Really, it's incorrect? I haven't written a triple-bar equivalence symbol, in the context of arithmetic, since the 70's. Pete St.John (talk) 18:49, 8 March 2008 (UTC)

For what it's worth, I believe it's not necessarily incorrect if the meaning of the symbol is clear. However, outside of books on finite fields and number theory, and especially in a Wikipedia article, the context is not clear enough for casual readers to understand what is happening. Also, in my understanding, = even in the right context is at best only shorthand, because 38 clearly is not equal to 14, just equivalent to 14. SilenceSoLoud (talk) 07:45, 5 March 2010 (UTC)
I just re-worded a line in the lead, as it used = instead of ≡. Since the correct symbol for the mathematical notation for a congruence relation has not yet been defined at this point in the article, I thought it best to phrase the line in English rather than to anticipate a symbol that has not yet been defined. As it was, with =, it was simply incorrect mathematical notation. I hope this makes the concept more clear. Based upon what I have read in various places in this talk page, this sort of thing has been an ongoing issue. — Anita5192 (talk) 06:20, 9 April 2014 (UTC)
Good move! Using the correct math symbol couldn't be done without having it defined first. Went ahead and expanded the lead section further, as it didn't make sense not to have the math symbol defined there as well. Hope you agree. — Dsimic (talk | contribs) 01:34, 11 April 2014 (UTC)

Integer remainder[edit]

I found it confusing to have .1666 as an example of the remainder. Using real numbers in the example is not a good choice when the rest of the article is about integers. Showing the same remainder with integer calculations would be more clear to me:

   38 = 3 ⋅ 12 + 2
   2 = 0 ⋅ 12 + 2

" ... For positive n and non-negative a and b, congruence of a and b can also be thought of as asserting that these two numbers have the same remainder after dividing by the modulus n. So,
    38 \equiv 2 \pmod {12}\,
because, when divided by 12, both numbers have the same remainder, .1666... (38/12 = 3.166..., 2/12 = .1666...). From the prior definition we also see that their difference, a - b = 36, is a whole number (integer) multiple of 12 ( n = 12, 36/12 = 3).

(Jonne6v (talk) 19:54, 22 April 2008 (UTC))


CAS Registry Example[edit]

This is really an application in coding theory and really has nothing whatsoever to do with chemistry, can this be rewritten as a more general coding theory example with something more familiar to most people? An ISBN perhaps? Absolt (talk) 15:31, 6 August 2008 (UTC)

This page is completely shagged.[edit]

None of the sums work. —Preceding unsigned comment added by 90.199.76.248 (talk) 14:39, 8 December 2008 (UTC)

How about adding the Algebraic formula?[edit]

Sorry, but I've been looking high and low for a formula to calculate the MOD() of a number. Is this the right place to suggest the addition of the following?

To emulate the function: z = MOD(x,y) use z = x-INT(x/y)*y

Many thanks

Graham Cattley —Preceding unsigned comment added by 61.29.101.176 (talk) 05:12, 6 January 2009 (UTC)

I've added section [Functional representation of the remainder] to your request and also added a few more things. Sonoluminesence (talk) 02:35, 3 March 2009 (UTC)

Citation request for first line[edit]

The first line in the article includes a frivolous citation request tag (as of the current version, it is asking for a citation for the claim that Gauss introduced modular arithmetic in 'Disquisitiones Arithmeticae'). Logically there's nothing to cite here: the work is cited right there if anyone wants to check whether he discussed it. If someone desires a proof that this was the first discussion of the topic, that's asking for a logical impossibility--"give me a citation proving that no one talked about this earlier," i.e. prove a negative. I'm deleting the citation tag. If anyone believes there's something wrong with the statement, I would invite them to just change it to cite the work that actually introduced the topic. JSoules (talk) 13:56, 18 June 2009 (UTC)

Python's % operator is not remainder.... more like modulo, but is its (mod n) correct for negative n?[edit]

Python's % operator gives negative results if the divisor/modulo is negative (e.g. 2%-5=-3; -5%-2=-1). Is this the right answer, or just Python weirdness?

i tested the two examples and the were correct acording to the anserw that you gave. i used python 2.6.2 60.228.200.114 (talk) 12:23, 18 January 2010 (UTC)
So does Excel's MOD(a,n) function. The rule is: if n>0, 0<=MOD(a,n)<n; if n<0, n<MOD(a,n)<=0; the sign of "a" plays no part in the sign of the result. Same thing in Matlab.
Also, the MOD function accepts all numbers, not just integers, the focus of this article. —Preceding comment added by Toolnut (talkcontribs) 18:29, 3 July 2010 (UTC)
APL (A Programming Language, dating back to the 1960's) also handles modulo in the same fashion. One argument for this is mod(a + k n, n) should produce the same result for any integer value of k, regardless if k is positive or negative. Rcgldr (talk) 08:09, 16 April 2012 (UTC)

Functional representation[edit]

This section looks many times better than when I first wrote it, thank you all! On another note, I removed the link to article

because it has nothing to do with this section. Sonoluminesence (talk) 17:01, 13 July 2009 (UTC)

193.146.151.121 (talk) 17:12, 5 July 2009 (UTC)Lurker #753

I found the following to be of dubious value, nay incorrect (see below), so I removed it to the discussion page:

Another functional representation uses sine and arcsine, taking advantage of the fact that arcsine is multivalued. Let
g(x) = \frac{2n}{\pi} \arcsin \left( \sin \left( \frac{\pi x}{2n} \right)\right).
Then
g(x) = x (mod n)
for 0 ≤ πx/2n < π/2 or π ≤ πx/2n < 3π/2, and
g(x) = −x (mod n)
for π/2 ≤ πx/2n < π or 3π/2 ≤ πx/2n < 2π.


I show this to be incorrect with one example. Consider x=\tfrac{2}{3}n , taken from the first domain of x, [0,n)\, . The argument to the "multi-valued arcsine" becomes \tfrac{\sqrt 3}{2} , and the solution set to \sin y = \tfrac{\sqrt 3}{2} \text{, in } [0,2\pi) \text{, is } y=\{\tfrac{\pi}{3},\tfrac{2\pi}{3}\} \text{, with } y=\tfrac{\pi}{2n}g(x) .

\therefore x = \frac{2}{3}n \Rightarrow g(x)=\left \{ \frac{2}{3}n+4mn, \frac{4}{3}n+4mn \right \}, m \text{ integer}

Clearly, \tfrac{2}{3}n is not congruent with \tfrac{4}{3}n+4mn , modulo n.
I have also made changes to the "mod" function definition so it applies to a negative modulus, as most such functions in the programming world do. I made it clear why this function is, by the provided definition, negative for negative modulus. Toolnut (talk) 04:46, 4 July 2010 (UTC)

Dear Toolnut, you write x=\tfrac{2}{3}n, ok then the expression: \frac{\pi x}{2n} = \frac{\pi}{3}, meaning:
sin(\frac{\pi}{3}) = 0.86602540
which has arcsin value arcsin(0.86602540) = 1.0471975511965 which in turn when you multiply by \frac{2n}{\pi} we get  1.0471975511965 * \frac{2n}{\pi} = \frac{2n}{3} which you must agree is congruent with himself \frac{2n}{3}.
What ever you are trying to prove is wrong, therefore I restored the section to its previous state. Please provide specific x and n, for which this formula fails if you want to reissue you delete. Thanks, Sonoluminesence (talk) 20:33, 4 August 2010 (UTC)
  1. First of all, the periodic mod function has jump discontinuities (sawtooth-shaped) that your sine function does not have.
  2. Secondly, the period of the mod function, mod(x, n), is n, whereas the period, say, X, of your function, g(x), is determined by the argument of the sine function changing by 2π: \tfrac{\pi X}{2n}=2\pi \therefore X=4n!
  3. Thirdly, you try to correct for these shortcomings by introducing complicated domains which do not work (even ranges where you define g(x) as being the negative of the mod funcion! Or is that not the mod function at all, but a congruence relation, with incorrect notation?). You say that "arcsine is multivalued" (striclty speaking, a "function," may not be "multivalued"), yet you have not noticed that its other value in [0,2π), for argument \tfrac{\sqrt 3}{2}, is \tfrac{2\pi}{3}. If you mean to use only the principal value of the inverse of the sine function (then, why call the arcsine "multivalued"), as calculators do, then its range should be confined to [\tfrac{-\pi}{2},\tfrac{+\pi}{2}], and your function g(x) takes the shape of a triangular (slope alternates between 1 and -1), not saw-toothed (slope is always +1, except at jump discontinuities), periodic function which crosses zero:
\text{for } 0\le x<n~,\ g(x)=x~; \text{ for } n\le x<3n~,\ g(x)=2n-x~; \text{ for } 3n\le x<4n~,~g(x)=x-4n
The mod function, as computed by most programs, is only negative when the modulus, n, is negative, and it does not cross zero with x. And how exactly are you addressing the fact that x can be greater than 3n, let alone its negative values which you entirely neglected in your definition and which most programs allow? I could go on, but this is taking too much effort. I'm sorry, but your formula makes less and less sense, the more I analyze it, and is not mathematically correct: you need to convince us that it is of value, or at least cite its source, if there is one.
4. Fourthly, by doing a simple restore, you also undid my other painstaking improvements to this section, which made the mod function definition conform to accepted practice in the computing world.

--Toolnut (talk) 02:58, 10 September 2010 (UTC)

To Gandalf61: Your undoing my entire work in favor of something simpler, though mathematically incorrect and non-enlightening, needs serious reconsidering. You are wrong in ignoring the signs of the two arguments to the mod function: they both affect the result in different ways. I have carefully read and noted the confusion and frustration in a few of the requests for clarification on this Discussions page, and have proceeded to explain the behavior of the mod function in as succinct a manner as possible. Please, try to build on my work, not just dismiss it out of hand: I am always open to suggestions. Toolnut (talk) 18:07, 10 September 2010 (UTC)

You are confusing mathematical functions with programming functions. Your poorly written description of the modulo operation from computer secience does not belong in this mathematics article. Gandalf61 (talk) 22:49, 10 September 2010 (UTC)
Gandalf61: I couldn't agree with you more that this is a math subject, and I don't know if you know that your treatment does not provide for the case where n is negative. I'd challenge you to find a way to address the result of applying the function definition without limitation as to the sign of n, because your function definition, as it stands, allows it to be negative, as well as for its arguments and return value to be all real. For mathematical rigor, there must also be a statement that n may not be zero, because the function is undefined there. We also need to name the function and its arguments in the equation: the floor function is not the mod function, and the variable b is not a function.
Secondly, computers do have a prominent role to play in math; just look at the previous section on "Remainders": three sentences were devoted there on how computing languages treat this operation. We need to expand on that to justify and accept the limitation in our choice of definition for the mod function.
As you can tell, I have spent considerable effort to make this little segment of the article as accurate and informative as possible. Please, don't erase my precious work, wholesale, and let's cooperate on this, if at all possible.Toolnut (talk) 05:41, 11 September 2010 (UTC)
The implementation of the mod function in computer languages has little to do with modular arithmetic. I'm not sure the "functional representation" section is that helpful, but the programming convention that a mod n takes the sign of n doesn't seem to be related to the purpose of the article, but is, in fact, dealt with properly in that equation. I edited the section to include the fact that the convention is that n is positive, but it may not be necessary. — Arthur Rubin (talk) 15:12, 11 September 2010 (UTC)

To Toolnut:

"First of all, the periodic mod function has jump discontinuities (sawtooth-shaped) that your sine function does not have."

By limiting x and n to be only natural numbers g(x) also has discontinuities. It doesn't matter how the "continues" function behaves in between legal points. Moreover, g(x) is not exactly the modulo operator, read my answer to your second argument.

"Secondly, the period of the mod function, mod(x, n), is n, whereas the period, say, X, of your function, g(x), is determined by the argument of the sine function changing by 2π: \tfrac{\pi X}{2n}=2\pi \therefore X=4n!"

Of course g(x) it has 4n period, because it describes a different function in every quadrant! Only in the first and third quadrants where sin and cos share the same sign g(x) is the modulo operator, and in other quadrants its the complement to x mod n. Put together, g(x) is expected to have 4n periods as it is constructed so that in every quadrant there are all the multiples of the following angle a, a = {pi/2n}, meaning {0 * pi/2n }, {1 * pi/2n}, ..., (n-1) * {pi/2n}. The 4n is the 4 quadrants!

"you try to correct for these shortcomings by introducing complicated domains which do not work (even ranges where you define g(x) as being the negative of the mod funcion!"

The negative is negative mod n, meaning n - (x mod n). It doesn't matter algebraically if you write n-(x mod n) or - (x mod n).

"You say that "arcsine is multivalued" (striclty speaking, a "function," may not be "multivalued")"

I did not write the multivalued word in the original post, it was added later by someone else and I would not object to omit it.

The little notation of g(x) is a fact, easily proven with drawing a circle, and dividing every quadrant to n equal parts. Moreover, I can come up with infinite many n and x for which this equation holds, while you can't come up with a single n and x that stands as a viable counter example.

I will allow two weeks for you (or anyone else) to state your objections if you have any, otherwise I will add g(x) again.

Thanks, Sonoluminesence (talk) 22:19, 16 September 2010 (UTC)

I don't see why it should be added. — Arthur Rubin (talk) 00:26, 17 September 2010 (UTC)
I agree. Unless there is a reliable source to show that this particular representation is especially notable, then I think it adds nothing useful to the article. Gandalf61 (talk) 07:00, 17 September 2010 (UTC)

Other names. Circular math[edit]

This is referred to as Circular math in DSP(Digital Signal Processing)[1] applications. I'm new to Wiki's and don't know the best way to make Circular math come up easier in search. [1]http://en.wikipedia.org/wiki/Circular_buffer Bill Arden (talk) 01:37, 23 October 2009 (UTC)

A Circular Buffer can be visualized in a somewhat similar manner, but Modular Arithmetic is really a separate topic. Modular arithmetic is about the ring Z/nZ in abstract algebra and number theory, fields of mathematics. Just about the only thing that a Circular Buffer shares with Modular Arithmetic is a vague notion of cyclicality and discreteness, which isn't enough to include it in this article.
Also, a google search for "circular math" turned up nothing relevant in any way. SilenceSoLoud (talk) 07:38, 5 March 2010 (UTC)

Is this the same as Non-Linear Arithmetic?[edit]

If it is, or is related to it, a clarification in the introduction should be made. —Preceding unsigned comment added by 129.215.5.254 (talk) 15:44, 15 July 2010 (UTC)

Added citation for euler and 'modern congruence'[edit]

I had a hard time finding this one due to so many cites copying what we (wikipedia) said. It looks like from a quick reading of this article that it does not depend on us at all. There is an extensive listing of citations at the end of it. —— nixeagleemail me 01:44, 29 August 2011 (UTC)

I've removed the reference to Euler's contribution. The citation discussed above does not mention modular arithmetic at all. From this article it seems clear that Euler did not develop the modern idea of congruence. Gauss was responsible, although it seems he was likely influenced by Euler's writing on remainder problems. Dillon128 (talk) 09:33, 4 May 2013 (UTC)

Residue Systems[edit]

Is this a typo? {-5,0,6,21} It seems that -5,0 makes sense, but the 6 and the 21 don't make sense to my limited understanding of this mod 4 example. I thought they had to be apart by multiples of 4, plus 1. Tullywinters (talk) 16:56, 21 January 2012 (UTC)

Looks fine to me. Think of it as {0,21,6,-5}, where the differences are multiples of 4 (positive or negative), plus 1. But it's not necessary to think of it that way; all you need to note is:
\left. 
\begin{array}{rcc}
 0 & \equiv & 0 \\
21 & \equiv & 1 \\
6 & \equiv & 2 \\
-5 & \equiv & 3 \\
\end{array} \right\rbrace \pmod 4
Arthur Rubin (talk) 18:11, 21 January 2012 (UTC)
{-5, 0, 6, 21} is a complete residue system modulo 4. All that is necessary is that each residue class is represented once and only once. — Anita5192 (talk) 18:15, 21 January 2012 (UTC)

There is an error in the LaTex[edit]

Under "The same rule holds for negative values" the first example should be mod 15 unless I am misunderstanding the material. -8 - 7 = -15 but the example says mod 5.

I am not capable of correcting this, but I'm sure someone here can.

Thanks! — Preceding unsigned comment added by 99.113.137.39 (talk) 17:55, 3 April 2013 (UTC)

It is not wrong to say -7 is congruent to 8 modulo 5, because -7-8 = -15 which is a multiple of 5. It would also be correct to say -7 is congruent to 8 modulo 15, or alternatively they are also congruent modulo 3 - you can take your pick. Gandalf61 (talk) 18:05, 3 April 2013 (UTC)

Residue class definition[edit]

Minor point: residue class is used before being defined. — Preceding unsigned comment added by 115.70.97.86 (talk) 05:13, 15 April 2013 (UTC)

Cryptography[edit]

Should there be a more detailed explanation for the uses of modular arithmetic in cryptography? such as another paragraph, there could also be a mention of it's use in the one-time pad cipher. — Preceding unsigned comment added by Thea10 (talkcontribs) 17:30, 27 June 2013 (UTC)

Almost all methods and algorithms of modern cryptography make use of modular arithmetic. Giving more details would amount to duplicate the articles on cryptography. D.Lazard (talk) 18:08, 27 June 2013 (UTC)
Then should the article say that "Almost all methods and algorithms of modern cryptography make use of modular arithmetic" — Preceding unsigned comment added by Thea10 (talkcontribs) 17:30, 27 June 2013 (UTC)

Section "Remainders"[edit]

This section seems [WP:OR]]: It contains wrong assertion like "dividing a negative number gives a negative remainder". It makes a subtle distinction between "=" and "≡", when there is no standard for using one symbol or the other ("≡" seems to me to be simply old fashioned). In fact the editor that has written this section tries to use these two symbols to make the distinction between (a = b) mod n and a = (b mod n) (these notations are also not standard, but have the advantage to be clear: the "mod" operator may be applied to a number to give the remainder and to an equality to assert that both members have the same remainder. The editor leaves also open the question that a mod n sometimes denotes an integer (the remainder) sometimes denote an equivalence class (modular integer), depending on the author and the context. I am unable to rewrite correctly this section. I have not removed it as WP:OR, because some clarification is really needed. This the reason of the tag "unreferenced". But I could also tag this section as "dubious". D.Lazard (talk) 16:39, 21 August 2013 (UTC)

Is (a + b) mod n equal to (a mod n) + (b mod n)[edit]

Hello. I was looking for some simple rules on addition, subtraction, etc. For example, is (a + b) mod n equal to ((a mod n) + (b mod n) mod n)? I know that g^(ab) mod n is equal to (g^a*g^b) mod n, and also equal to ((g^a nod n) * (g^b mod n) mod n). Perhaps some simple rules and examples for a layman would be very helpful rather than all the abstract notations. — Preceding unsigned comment added by 98.117.57.26 (talk) 01:10, 10 September 2013 (UTC)

You may find these rules in Modulo operation#Equivalencies. IMO, this article deserve to be merged with modulo operation and rewritten in the following way: first define a mod n as the remainder of the Euclidean division of a by n, and then define ab (mod n) as an abbreviation for a mod n = b mod n. By the way, this would solve the issue raised in my preceding post. D.Lazard (talk) 09:04, 10 September 2013 (UTC)

Bizzarro "Expand French" Tag[edit]

So, what's the point to it?. We could say the same thing for just about any article and any language, but we don't because it's a universal unexceptional fact that would be silly to put at the top of every article. The original tagger (July 2012) didn't justify it in the edit comment. There's been no discussion of it on this talk page nor in its archive going back to 2002 -- the word "French" doesn't appear anywhere until the title of this section. So what's so special about this case to justify yet another weirdo tag (unencyclopedic behind-the-curtain distraction)?

I noted that someone actually did try some translation from the French article, 551 characters were added in November 2012. But, the fact that someone actually followed through a little bit isn't justification for the tag. We still need to justify in the first place why this article can have the distracting thing while others don't.

If there really is no exceptional justification, or if most of what can be squeezed out of the French article has already been squeezed out, then the tag should be removed. If there really is some exceptional justification, maybe that should be recorded with some hidden text or something since nothing about it was mentioned by the original tagger in 2012 (nor by anyone else anywhere ever).

108.7.11.145 (talk) 06:31, 18 September 2013 (UTC)

This tag means that the French article is much more developed and contains much more information than the English one. In particular (this is only one example among several), the long history section of the French article is completely lacking here. This cannot be said for any article and any language. This tag is not a "unencyclopedic behind-the-curtain distraction" and may be useful for the common reader: it says that, if he can understand French, he will find much more encyclopedic information in the French article.
Apparently you have read only the source code of the tag, without looking how it appears in the article.

D.Lazard (talk) 09:48, 18 September 2013 (UTC)


That's a nice explanation. It's high minded and good (really). But, that's not what that tag says. If what you say about the reason for the tag is true (it probably is), then the French article can easily be referenced in "External links", or "References", etc., just like the way it's done in every other other WP article. It can even be (smoothly) mentioned prominently and linked in the text.

For any particular WP article, many sources have much more information than the article. Our situation is nothing new or exceptional. To pick one of those many sources and highlight it beyond all norms instead of treating it normally is, like I suggested, unencyclopedic and a big distraction right up front.

If we want to leave the message as-is (i.e. asking to incorporate material from FWP, vs. mentioning a good "further reading" source), then the tag is much more suited for the top of the talk page. That way, the behind-the-scenes sausage ingredients are hidden behind the scenes where it is not a distraction, but it's still prominent for those who would want to see the message.

Incidentally, I re-checked how the tag appears in the article. The tag appears just as I was thinking it appeared when I wrote the above note. (My addled brain frequently fails me that way, but it hadn't this time.) Both the tag and its drop-down "show" button" refer only to incorporating material from FWP, not to how the source is a wonderful font for interesting further reading.

108.7.11.145 (talk) 20:04, 18 September 2013 (UTC)
Cite error: There are <ref> tags on this page, but the references will not show without a {{reflist}} template (see the help page).