Drexel dragonThe Math ForumDonate to the Math Forum

Ask Dr. Math - Questions and Answers from our Archives
_____________________________________________
Associated Topics || Dr. Math Home || Search Dr. Math
_____________________________________________

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.
Associated Topics:
High School Number Theory

Search the Dr. Math Library:


Find items containing (put spaces between keywords):
 
Click only once for faster results:

[ Choose "whole words" when searching for a word like age.]

all keywords, in any order at least one, that exact phrase
parts of words whole words

Submit your own question to Dr. Math

[Privacy Policy] [Terms of Use]

_____________________________________
Math Forum Home || Math Library || Quick Reference || Math Forum Search
_____________________________________

Ask Dr. MathTM
© 1994-2013 The Math Forum
http://mathforum.org/dr.math/