ôô

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.

By
Jason Marshall, PhD,
Episode #054

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 x 7 = 56 is a little less than 62, and 8 x 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.

Pages

The Quick and Dirty Tips Privacy Notice has been updated to explain how we use cookies, which you accept by continuing to use this website. To withdraw your consent, see Your Choices.