20051023, 09:56  #1 
Jun 2005
Near Beetlegeuse
2^{2}×97 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, F1). 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 = F1(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, 
20051023, 12:05  #2  
Apr 2004
Copenhagen, Denmark
116_{10} Posts 
Quote:
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,F1] 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 20051023 at 12:09 

20051023, 12:11  #3 
"Nancy"
Aug 2002
Alexandria
2,467 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 ab 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 
20051023, 12:12  #4 
"Nancy"
Aug 2002
Alexandria
2,467 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 20051023 at 12:15 
20051023, 15:05  #5 
Jun 2005
Near Beetlegeuse
2^{2}×97 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. 
20051023, 17:05  #6 
"Phil"
Sep 2002
Tracktown, U.S.A.
10001011111_{2} Posts 
Just a quick additional note 
Programming language conventions often define a mod q to be the unique representative in the range 0, 1, ..., q1, 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. 
20051023, 21:17  #7  
∂^{2}ω=0
Sep 2002
República de California
2^{2}×5×587 Posts 
Quote:


20051024, 04:07  #8 
"Nancy"
Aug 2002
Alexandria
2,467 Posts 
Cute exercise: what does a == b (mod 0) mean?
Alex 
20051024, 06:04  #9 
"Richard B. Woods"
Aug 2002
Wisconsin USA
1111000001100_{2} Posts 
It means a = b.
Reasoning: a == b (mod 0) => ab = a multiple of 0. 0 is the only multiple of 0. Therefore ab = 0. Corollary: In mod 0, each equivalence class contains only a single number. Last fiddled with by cheesehead on 20051024 at 06:16 
20051024, 06:27  #10 
"Nancy"
Aug 2002
Alexandria
2,467 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 welldefined, but a remainder after division by 0 is not. Alex Last fiddled with by akruppa on 20051024 at 06:39 
20051024, 18:23  #11  
"Richard B. Woods"
Aug 2002
Wisconsin USA
7692_{10} Posts 
Quote:
Recently I realized that {breakingmodifying} nolongeruseful habits was likely to be my toughest ongoing task for the rest of my life. Last fiddled with by cheesehead on 20051024 at 18:27 

Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Basic Number Theory 5: rationals & intro to modular arithmetic  Nick  Number Theory Discussion Group  1  20161021 22:21 
modular arithmetic  science_man_88  Miscellaneous Math  42  20110726 02:02 
modular arithmetic problem  JuanTutors  Math  4  20090311 16:06 
need C/C++ modular arithmetic code for Windows  ixfd64  Programming  15  20080730 03:52 
Jim Howell's modular arithmetic program?  ixfd64  Software  0  20040527 05:42 