Modulo a Divisor ... that's Negative?
Date: 04/02/2012 at 03:16:12 From: Jason Subject: Modulo Let us take a simple problem: 17 mod 10 We can find the solution to this very easily by long division. The remainder here will be 7. Let us make things a little bit more complicated: -17 mod 10 If we long divide -17/10, we can reduce this to 10(1) = 10 > -17 We can't subtract that from -17, so let's take 10(-1) = -10 > -17 We can't subtract that, either. So try 10(-2) = -20 < -17 Now we have the number we need to subtract, so let's subtract. -17 - (-20) = -17 + 20 = 3 -17 mod 10 = 3 Now let's take another problem: 17 mod(-10) This, I can't for the life of me figure out how to do. Seventeen mod(-10) means 17/-10, so we do long division. But how do we determine what number to subtract from 17? We can choose any x such that x < 1.7, and multiply that by 10 to get 10(x), and it will work. We will get remainder zero when x = 1.7. But how do we know to say that we are going to choose x to be -2 and the remainder will work out like this? 17 - (-10(-2)) = 17 - 20 = -3. I am stumped. I have no idea.
Date: 04/02/2012 at 13:25:21 From: Doctor Vogler Subject: Re: Modulo Hi Jason, Thanks for writing to Ask Dr. Math. I should first like to point out that mathematicians and computer scientists tend to think of "mod" in different ways. Computer scientists usually think of "mod" as an operation, like multiplication and division, which returns the remainder. The usual way to define mod is this, where x div y (integer division) is the quotient when you divide x by y: x mod y = x - y*(x div y) So you can answer your question if you can figure out the quotient that you get when you divide 17 by -10. In fact, there are many ways to define the quotient of a division problem. My personal favorite is x div y = floor(x/y) This means to round toward negative infinity. So ... 17 div 10 = 1 ... but -17 div 10 = -2 Many computers prefer the absolute values to be independent of the signs, so they will instead round toward zero. This is sometimes called truncation. On the other hand, particularly when you don't need a perfect answer, it is often preferable to round to the nearest integer, so that ... 17 div 10 = 2 ... but 13 div 10 = 1 And some people want the sign of y to affect which way to round, while others don't. Either choice for the quotient will give a corresponding definition of "mod," and none is really "more correct" than the other, as each has its usefulness in certain applications. Mathematicians, on the other hand, think of mod differently. Mathematicians think of mod as a type of number, so the integer "3" is different from the modular number "3 mod 10." And mathematicians speak of equivalence, or congruence, of such numbers when they are the same. So the mathematician would write this: -17 = 3 mod 10 Here, the equals sign means congruence or equivalence; the "mod 10" tells what kind of congruence you are talking about; and this equation is meant to say that -17 and 3 are actually the same thing, mod 10. So it would also be correct to say -17 = -7 mod 10. After all, -7 is also equal to 3 mod 10. Indeed, so are 13 and 17583, and infinitely many others. Often, this type of expression is defined by saying that this ... a = b mod m ... means that the difference a - b is divisible by m. By this interpretation of mod, any of the definitions I listed above, which computer scientists might use, will give correct answers, in that they give answers congruent to x mod y; and their difference is the other properties that they hold, such as the answer z satisfying 0 <= z < |y| (my favorite), or 2|z| <= |y|, or something else. Anyway, to a mathematician, "mod m" means exactly the same thing as "mod(-m)." You can check that a - b is divisible by m if and only if a - b is divisible by -m. So "mod(-10)" means the same thing as "mod 10" to a mathematician, but he would also say that any of the numbers is congruent to 17 mod -10 -13, -3, 7, 17, 27, 37, 47, etc. It is, however, common for a mathematician to speak of the "least positive residue," which means the remainder z mod y that satisfies 0 <= z < |y|. So this would correspond to the "round toward negative infinity" choice of integer division, and the least positive residue of 17 mod -10 would be 7. If you have any questions about this or need more help, please write back and show me what you have been able to do, and I will try to offer further suggestions. - Doctor Vogler, The Math Forum http://mathforum.org/dr.math/
Date: 04/02/2012 at 17:50:30 From: Jason Subject: Thank you (Modulo) Thanks a million. You have been very helpful. I can't thank you enough.
Search the Dr. Math Library:
Ask Dr. MathTM
© 1994- The Math Forum at NCTM. All rights reserved.