Hey, I'm Josh Kayani, a student and fledgling software developer. Here, I rant and rave about tech and other topics.
Last semester, a friend and I were taking Discrete Math (counting, sets, logic, etc.), and he asked me a question about how modulus worked with negative numbers. It took me a bit to come up with a good answer, and I think it provides a nice framework for understanding how that operation works as a whole, so here goes.
When someone’s asked to calculate , they’re being asked what the remainder would be when dividing by . For example, calculating would be , since can only “go into” twice, and there will be left over .
We can make this a little more mathematical (it comes in handy when extending this to negative numbers): when calculating , you’re trying to find the value such that , where is the largest possible integer such that is greater than . Again, consider calculating : here, we’re trying to find the largest that when multiplied by , is still less than . If , then equals , and is not greater than . However, if , then equals , and is greater than . Plugging this into our equation, we find that , which means equals .
To understand where that model came from, think about what divisibility means. If 2 numbers, and are divisible, it means that yields no remainder; in other words, there is some integer such that . Using that same model, we can calculate the remainder of any division by taking , since this tells us how far was from .
Now to answer the question: how do we calculate ? Our model remains the same; we’re still trying to find using the equation above, and should still be the largest possible integer so that . The key is in this last expression; for a negative integer to be greater than another integer , should be negative but have a larger absolute value. For example, is larger than all the integers in the range to , but all those numbers have a larger absolute value than (). With negative numbers, larger absolute values mean the number gets smaller – exactly the opposite of what happens with positive numbers.
Taking this into account, consider versus . The largest that can be multiplied by to be less than 7 is , giving us . But the largest that can be multiplied by and be less than is , since is greater than (), so our answer becomes . From this, we can see that there is no shortcut like: calculate and then multiply it by .
This is a lot of math to do a basic operation, so here’s a shortcut. When calculating , and is positive, you can simply find the closest multiple of that is still less than (absolute value of ), call it , and do to get your answer. When is negative however, you should still find the closest multiple of that is less than , call it , but then do to get your answer. This just comes from applying the above model.
You can also think of this in terms of going “under” and “over”; with , you’re going “under” to find , and taking the difference . With , you’re going “over” to find , and again taking the difference .
Hopefully I managed to articulate all of that well!