DIVISION IN MODULAR ARITHMETIC You always have three options for how to calculate a/b (mod n): 1) Trial and Error: Is 1xb = a?, is 2xb = a?, is 3xb = a?, .... 2) Backwards Euclidean Alg: Solve bx + ny = a for x. 3) Multiply by 1/b (mod n), if you know what 1/b (mod n) is. The method you should choose depends on what information you've been given. 1) Trial and Error: ------------------- For example, if you are given a multiplication table, then (1) Trial and Error is definitely the easiest method. That is, all the answers 1xb, 2xb, 3xb, 4xb, 5xb, ... are already written out for you in the "b column", so all you have to is to look down that column until you find a, and then see what row a is on. Trial and error is also good even without a multiplication table if N IS SMALL. For example, if n = 5, then you should absolutely do trial and error, because there are only 4 numbers to check. Another (and often faster) version of trial and error for division involves looking at successive values of a (mod n), by continuing to add n to a, and waiting until you find an "a" that is divisible by b (or even that allows you to reduce the fraction a/b). For example: 3 56 (=3+53) 7 60 (=7+53) --- == ---------- == - == ---------- == 30 (mod 53). 16 16 2 2 2) Backwards Euclidean Algorithm: --------------------------------- As n gets much larger, you'll want to consider using the (2) Backwards Euclidean Algorithm. Why? Well, let's see.... a/b = x (mod n) 11/14 = x (mod 31) a = bx (mod n) 11 = 14x (mod 31) a = bx + ny for some y. 11 = 14x + 31y for some y. This is one linear equation in 2 variables, so it is precisely the sort of equation we learned how to solve using the Backwards Euclidean Algorithm. Doing this gives us a solution for x and y, and all we care about is x. Let's try this out with the above example with 11/14 (mod 31). To solve 11 = 14x + 31y, we first do the Euc. Alg for 14, 31. a) 31 = 2 x 14 + 3 ---> 3 = 31 - 2 x 14 -- -- - - -- -- b) 14 = 4 x 3 + 2 ---> 2 = 14 - 4 x 3 -- - - - -- - c) 3 = 1 x 2 + 1 ---> 1 = 3 - 1 x 2 - - - - - - so gcd(31,14) = 1. Backwards: Start with (c). 1 = 3 - 1 x 2 - - - Sub (b) for 2. = 3 - 1 x (14 - 4 x 3) - - -- - Collect terms. = -1 x 14 + 5 x 3 -- - Sub (a) for 3. = -1 x 14 + 5 x (31 - 2 x 14) - -- -- -- Collect terms. 1 = 5 x 31 + (-11) x 14. - -- -- Recall that we wanted to solve 11 = 14x + 31y, so we multiply the last equation by 11 to obtain 11 = 55 x 31 + (-121) x 14. Thus we get x = -121. Finally, we must represent x mod 31. -121 = -4 x 31 + 3, so x = 121 = 3 (mod 31). Let us check this. We claimed that 11/14 = 3 (mod 31). Then we must have 11 = 14 x 3 (mod 31). This works correctly, because 14 x 3 = 42 = 31 + 11. 3) Multiply by 1/b (mod n). --------------------------- It is rare that you will already be told what 1/b is, but this is precisely what you are told in Homework 16, problem 3, so make the most of it. Recall that a/b = a x (1/b), so, for example, if we know that 1/5 = 3 (mod 7), then 2/5 = 2 x 1/5 = 2 x 3 = 6 (mod 7). Check that this works: 5 x 6 = 30 = 4 x 7 + 2. Good. This is sort of like multiplying by .5 instead of dividing by 2, except that in this case, multiplying is a billion times easier than dividing, because that's just the way that modular arithmetic works. When might you start out knowing 1/b if you weren't already told the answer like in Homework 16, problem 3? Well, if you want to divide by b a lot in some fixed base, then you should really only do a hard division problem _once_. Figure out 1/b once, and then for all the other a/b examples you want to calculate, just multiply a x (1/b). For example, in part (2) of this discussion, when we calculated that 11/14 = 3 (mod 31), we first obtained the equation 1 = 5 x 31 + (-11) x 14. - -- -- Well, this is precisely the equation we need for finding the reciprocal of 14. This equation says that (-11) x 14 = 1 (mod 31), so 1/14 = -11 = 20 (mod 31). Given that 1/14 = 20 (mod 31), it should be easy to calculate anything/14 (mod 31). For example, 11/14 = 11 x 20 = 220 = 7 x 31 + 3 = 3 (mod 31) (as shown before) 28/14 = 28 x 20 = 560 = 18 x 31 + 2 = 2 (mod 31). Okay, that summarizes the 3 techniques for division. Deciding which one to use is up to you, but usually it's best to use the method that will take the least amount of time.