mersenneforum.org > Math Modular Arithmetic
 Register FAQ Search Today's Posts Mark Forums Read

 2005-10-23, 09:56 #1 Numbers     Jun 2005 Near Beetlegeuse 38810 Posts Modular Arithmetic My understanding of modular arithmetic is that when working modulo F (where F is a positive integer) the answer can only be in the range (0, F-1). But on the mersennewiki and elsewhere I have seen examples of the answer being given as = -1(Mod F). Up to this point I have interpreted that as meaning = F-1(Mod F) but I have arrived at the point where I would prefer to have that confirmed. Am I correct in my understanding? Saw it here, for example: http://www.mersennewiki.org/index.php/P%C3%A9pin_Test Thank you,
2005-10-23, 12:05   #2
JHansen

Apr 2004
Copenhagen, Denmark

22·29 Posts

Quote:
 Originally Posted by Numbers My understanding of modular arithmetic is that when working modulo F (where F is a positive integer) the answer can only be in the range (0, F-1). But on the mersennewiki and elsewhere I have seen examples of the answer being given as = -1(Mod F).
When working modulo a number, say F, all the integers are divided into classes. When you then talk about a number modulo F, you are really talking about an equivalence class.

An example will clarify: Let F=5. Then all the integers are divided into 5 classes: Those who leave a remainder of 0 when divided by 5 (i.e: ...,-10,-5,0,5,10,...), those who leave a remainder of 1 when divided by 5 (i.e. ...,-9,-4,1,6,...) and so on. Thus when you write 1 (mod 5) you are really talking about the set of numbers (...,-9,-4,1,6,...) and not a single number.

It doesn't take long before people get tired of writing (...,-9,-4,1,6,...) and choose a representative for the class. Often the number in the interval [0,F-1] which belongs to the class is chosen.

Thus -1 (mod 5) = the class of (...,-11,-6,-1,4,...) = 4 (mod 5) and so on.

--
Cheers,
Jes H

Last fiddled with by JHansen on 2005-10-23 at 12:09

 2005-10-23, 12:11 #3 akruppa     "Nancy" Aug 2002 Alexandria 25·7·11 Posts You are correct. The whole story, in brief: The modulo m operation defines an equivalence relation, where two integers a,b are considered equivalent if a-b is a multiple of m. These integers are said to be in the same equivalence class. For the modulus m, there are m different equivalence classes. I.e. modulo 5, they are: {0,5,-5,10,-10,15,-15,...} {1,6,-4,11,-9,16,-14,...} {2,7,-3,12,-8,17,-13,...} {3,8,-2,13,-7,18,-12,...} {4,9,-1,14,-6,19,-11,...} You can see that every integer falls into exactly one equivalence class. So saying "a == -1" really means: "a is in the same equivalence class as -1". If your modulus is 5, this is the same as saying "a == 4", "a == -11", "a == 10000004", etc. The individual elements of an equivalence class are called "representatives" when you use them to identify which class you mean, i.e. in your congruence a == -1, the integer -1 is used as the representative of the class it is in. Alex
 2005-10-23, 12:12 #4 akruppa     "Nancy" Aug 2002 Alexandria 25·7·11 Posts Jes: Lol! Great minds, and all... Alex Edit: Why is this in Miscellaneous? It's a perfectly valid question, properly posed - not like crackpottery at all! Moved into "Math". Last fiddled with by akruppa on 2005-10-23 at 12:15
 2005-10-23, 15:05 #5 Numbers     Jun 2005 Near Beetlegeuse 1100001002 Posts Seems I was right, but not for the reason I thought, which makes me glad I asked. Thank you both for very good answers.
 2005-10-23, 17:05 #6 philmoore     "Phil" Sep 2002 Tracktown, U.S.A. 22·32·31 Posts Just a quick additional note - Programming language conventions often define a mod q to be the unique representative in the range 0, 1, ..., q-1, although if a is negative, it can be defined differently. I think that this sometimes leads to confusion among those who learn about the mod operation from computer manuals or textbooks. Thanks for the explanations, Jes and Alex.
2005-10-23, 21:17   #7
ewmayer
2ω=0

Sep 2002
República de California

9,791 Posts

Quote:
 Originally Posted by philmoore Just a quick additional note - Programming language conventions often define a mod q to be the unique representative in the range 0, 1, ..., q-1, although if a is negative, it can be defined differently. I think that this sometimes leads to confusion among those who learn about the mod operation from computer manuals or textbooks. Thanks for the explanations, Jes and Alex.
IIRC some languages define separate "mod" and "modulo" operations, where one gives an answer strictly in [0, q-1] and the other gives the equivalent number closest to zero which shares the same sign as the input.

 2005-10-24, 04:07 #8 akruppa     "Nancy" Aug 2002 Alexandria 9A016 Posts Cute exercise: what does a == b (mod 0) mean? Alex
 2005-10-24, 06:04 #9 cheesehead     "Richard B. Woods" Aug 2002 Wisconsin USA 22×3×599 Posts It means a = b. Reasoning: a == b (mod 0) => a-b = a multiple of 0. 0 is the only multiple of 0. Therefore a-b = 0. Corollary: In mod 0, each equivalence class contains only a single number. Last fiddled with by cheesehead on 2005-10-24 at 06:16
 2005-10-24, 06:27 #10 akruppa     "Nancy" Aug 2002 Alexandria 25×7×11 Posts Correct. This example shows that that the definition that uses a difference is more general than the definition that uses a remainder after division. Saying that the difference is a multiple of zero is well-defined, but a remainder after division by 0 is not. Alex Last fiddled with by akruppa on 2005-10-24 at 06:39
2005-10-24, 18:23   #11

"Richard B. Woods"
Aug 2002
Wisconsin USA

22×3×599 Posts

Quote:
 Originally Posted by akruppa Saying that the difference is a multiple of zero is well-defined, but a remainder after division by 0 is not.
So accustomed am I to the definition using division that I actually first posted a foolish comment that a == b (mod 0) had no meaning because ... but then thought, "Alex wouldn't have posted that exercise just to invite that response ... Oh, now I see the point of the different definition."

Recently I realized that {breaking|modifying} no-longer-useful habits was likely to be my toughest ongoing task for the rest of my life.

Last fiddled with by cheesehead on 2005-10-24 at 18:27

 Similar Threads Thread Thread Starter Forum Replies Last Post Nick Number Theory Discussion Group 1 2016-10-21 22:21 science_man_88 Miscellaneous Math 42 2011-07-26 02:02 JuanTutors Math 4 2009-03-11 16:06 ixfd64 Programming 15 2008-07-30 03:52 ixfd64 Software 0 2004-05-27 05:42

All times are UTC. The time now is 08:46.

Fri Oct 23 08:46:56 UTC 2020 up 43 days, 5:57, 0 users, load averages: 1.88, 1.52, 1.38

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.