mersenneforum.org  

Go Back   mersenneforum.org > Great Internet Mersenne Prime Search > Math

Reply
 
Thread Tools
Old 2005-10-23, 09:56   #1
Numbers
 
Numbers's Avatar
 
Jun 2005
Near Beetlegeuse

18416 Posts
Default 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,
Numbers is offline   Reply With Quote
Old 2005-10-23, 12:05   #2
JHansen
 
JHansen's Avatar
 
Apr 2004
Copenhagen, Denmark

22·29 Posts
Default

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
JHansen is offline   Reply With Quote
Old 2005-10-23, 12:11   #3
akruppa
 
akruppa's Avatar
 
"Nancy"
Aug 2002
Alexandria

2,467 Posts
Default

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
akruppa is offline   Reply With Quote
Old 2005-10-23, 12:12   #4
akruppa
 
akruppa's Avatar
 
"Nancy"
Aug 2002
Alexandria

2,467 Posts
Default

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
akruppa is offline   Reply With Quote
Old 2005-10-23, 15:05   #5
Numbers
 
Numbers's Avatar
 
Jun 2005
Near Beetlegeuse

22×97 Posts
Default

Seems I was right, but not for the reason I thought, which makes me glad I asked.

Thank you both for very good answers.
Numbers is offline   Reply With Quote
Old 2005-10-23, 17:05   #6
philmoore
 
philmoore's Avatar
 
"Phil"
Sep 2002
Tracktown, U.S.A.

1,117 Posts
Default

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.
philmoore is offline   Reply With Quote
Old 2005-10-23, 21:17   #7
ewmayer
2ω=0
 
ewmayer's Avatar
 
Sep 2002
Rep├║blica de California

2·13·443 Posts
Default

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.
ewmayer is offline   Reply With Quote
Old 2005-10-24, 04:07   #8
akruppa
 
akruppa's Avatar
 
"Nancy"
Aug 2002
Alexandria

2,467 Posts
Default

Cute exercise: what does a == b (mod 0) mean?

Alex
akruppa is offline   Reply With Quote
Old 2005-10-24, 06:04   #9
cheesehead
 
cheesehead's Avatar
 
"Richard B. Woods"
Aug 2002
Wisconsin USA

22·3·641 Posts
Default

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
cheesehead is offline   Reply With Quote
Old 2005-10-24, 06:27   #10
akruppa
 
akruppa's Avatar
 
"Nancy"
Aug 2002
Alexandria

2,467 Posts
Thumbs up

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
akruppa is offline   Reply With Quote
Old 2005-10-24, 18:23   #11
cheesehead
 
cheesehead's Avatar
 
"Richard B. Woods"
Aug 2002
Wisconsin USA

170148 Posts
Default

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
cheesehead is offline   Reply With Quote
Reply

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 2016-10-21 22:21
modular arithmetic science_man_88 Miscellaneous Math 42 2011-07-26 02:02
modular arithmetic problem JuanTutors Math 4 2009-03-11 16:06
need C/C++ modular arithmetic code for Windows ixfd64 Programming 15 2008-07-30 03:52
Jim Howell's modular arithmetic program? ixfd64 Software 0 2004-05-27 05:42

All times are UTC. The time now is 22:59.

Wed Sep 30 22:59:12 UTC 2020 up 20 days, 20:10, 0 users, load averages: 2.09, 1.97, 1.78

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, Jelsoft Enterprises Ltd.

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.