How to Do Multiplication and Division in Modular Arithmetic
Learn more about performing modular arithmetic, how it’s related to finding remainders in division, and how it can help you predict the future.
Jason Marshall, PhD
Listen
How to Do Multiplication and Division in Modular Arithmetic
In response to the last article on modular arithmetic, math fan Jeff left a comment on the Math Dude’s Facebook page saying that his daughter had been given the problem of figuring out what day of the week it would be a certain number number of days from today. After starting to count off all the days one by one, Jeff introduced her to modular arithmetic…and she was very excited since it made the problem much easier to solve. But what exactly about modular arithmetic made this so much easier? Well, keep on reading because today we’re going to begin to figure this out.
Recap: What is Modular Arithmetic?
Before we answer this question, let’s take a few minutes to finish off the introduction to modular arithmetic that we began in the last article. As you’ll recall, modular arithmetic is a form of arithmetic for integers in which the number line that we count on is wrapped around into a circle whose length is given by a number called the modulus. For example, in arithmetic modulo 12, like what we have when adding numbers on a normal 12-hour clock, a problem like 10 + 5 (mod 12) has the answer 3 (and not 15) since once we count up to 12 we start over at 1 again.
Okay, that’s how addition works in modular arithmetic. But there’s a lot more to arithmetic than just addition, so let’s now take a look at how the other arithmetic operations work in modular arithmetic too.
How Subtraction Works in Modular Arithmetic
Up first: subtraction. This one is pretty easy, actually…so long as you have a good understanding of how to think about doing modular addition. And that’s because—just as with normal non-modular arithmetic—modular subtraction is basically the opposite of modular addition. Whereas you can think of modular addition as counting forward in the clockwise direction around the face of a “clock,” you can think of modular subtraction as counting backward around that “clock.”
For example, what’s (2 – 4) (mod 12)? Well, all you have to do is think about starting at 2 on a normal 12-hour clock, and then counting backwards 4 numbers: from 2 to 1, then to 12, 11, and finally 10. So (2 – 4) (mod 12) ≡ 10. Remember, the “≡” symbol here means these things are “congruent”—which is a word we use so we don’t get confused with the idea of “equality” in normal arithmetic.
Okay, how about arithmetic modulo 5: What’s (2–4) (mod 5)? Well, in this case, you need to think of a clock that has a zero at the top and then a 1, 2, 3, and 4 going around it in a clockwise direction. So, starting at 2 on this clock and working backwards 4 spaces—1, 0, 4, 3—we find that (2–4) (mod 5) ≡ 3.
How Multiplication and Division Work in Modular Arithmetic
Now that we can do both addition and subtraction, we just need to figure out how multiplication and division work in modular arithmetic. All you need to do is first figure out the answer to your multiplication or division problem using normal non-modular arithmetic, and then convert that number into its modular form. In other words, to find the answer to (3×7)(mod 12), first figure out what 3×7 is in regular arithmetic—it’s 21. Next, figure out what 21 is congruent to in math modulo 12. You can find the answer by starting at 0 on a normal 12-hour clock and then counting clockwise 21 spaces. Eventually, you’ll arrive at 9. That’s all there is to it! And division works the same way.
How is Modular Arithmetic Related to Remainders in Division?
Though that method of multiplying and dividing numbers in modular arithmetic works, it’s not exactly efficient. For example, what if you needed to find (1,550 / 25) (mod 8)? Well, you could first find that 1,550 / 25 = 62 using normal non-modular arithmetic, and then count out 62 spaces on a modulus 8 clock to figure out where you end up. But that’s going to take a while!
The good news is that there is a more efficient way to do things. As before, the first step in solving a problem is to find the answer using normal arithmetic. So for (1,550 / 25) (mod 8) you still start by figuring out that 1,550 / 25 = 62. Now, instead of counting hour by hour around a modulus 8 clock—a rather time consuming and error prone process—what we can instead figure out is what the leftover bit is going to be after going around that modulus 8 clock a certain number of times. In other words, we need to do division and figure out the remainder.
In this problem, we know that 8 goes in to 62 a little more than 7 times—since 8×7=56 is a little less than 62, and 8×8=64 is a little bit more. That means that after going around the modulus 8 clock 7 times (that is, through 56 numbers), we still need to count through 6 more numbers to make 62 in total. In other words, the answer to (1,550 / 25) (mod 8) must be the remainder left over in the problem 62/8. So, (1,550/25) (mod 8)=62(mod 8) ≡ 6.
Let’s try another one. Say you want to find 20 (mod 6). You just need to find the remainder to the problem 20/6. Since 20/6=3 remainder 2, 20 (mod 6)≡ 2. Or, to find 109 (mod 7), you just need to find that 109/7=15 remainder 4. Therefore, 109 (mod 7) ≡ 4.
Practice Problems
So what about the problem that Jeff’s daughter was confronted with…the one about finding the day of the week some number of days from today? Well, unfortunately we’re out of time, so I’m going to let you think about how what we’ve talked about today can help solve that problem—and we’ll talk about how to figure it all out in the next article.
But before we finish, here are a couple of practice problems for you to work on to help you make sure you understand everything we’ve talked about:
-
What’s (150 + 25) (mod 10)?
-
What’s (150 – 25) (mod 10)?
-
What’s (150 x 25) (mod 10)?
-
What’s (150 / 25) (mod 10)?
Use the connection between modular arithmetic and the remainder in division to solve these problems. You can find the answers at the very end of the article. After checking them, feel free to leave a comment at the bottom of the page and let me know how you did.
Wrap Up
If you have questions about how to solve these practice problems or any other math questions, please email them to me at mathdude@quickanddirtytips.comcreate new email, send them via Twitter, or become a fan of the Math Dude on Facebook and get help from me and the other math fans there.
Until next time, this is Jason Marshall with The Math Dude’s Quick and Dirty Tips to Make Math Easier. Thanks for reading math fans!
Practice Problem Answers
-
Since 150 + 25 = 175, (150 + 25) (mod 10) = 175 (mod 10). The remainder in 175 / 10 is 5, therefore (150 + 25) (mod 10) ≡ 5.
-
Since 150 – 25 = 125, (150 – 25) (mod 10) = 125 (mod 10). The remainder in 125 / 10 is 5, therefore (150 – 25) (mod 10) ≡ 5.
-
Since 150 x 25 = 3750, (150 x 25) (mod 10) = 3750 (mod 10). The remainder in 3750 / 10 is 0, therefore (150 x 25) (mod 10) ≡ 0.
-
Since 150 / 25 = 6, (150 / 25) (mod 10) = 6 (mod 10). The remainder in 6 / 10 is 6, therefore (150 / 25) (mod 10) ≡ 6.
Clock image from Shutterstock
About the Author
Jason Marshall is the author of The Math Dude’s Quick and Dirty Guide to Algebra. He provides clear explanations of math terms and principles, and his simple tricks for solving basic algebra problems will have even the most math-phobic person looking forward to working out whatever math problem comes their way.