ôô

# How to Do Multiplication and Division in Modular Arithmetic By
Jason Marshall, PhD
Episode #54

## 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 