Java modular division

1
votes

I'm doing some error correcting, and I need to divide two digits under mod 11 in Java.

Now this I know, from using a modular calculator:

9/1 mod 11 = 9
2/10 mod 11 = 9

The problem comes in getting Java to calculate this. In Java:

(9 / 1) % 11 = 9 - This is fine
(2 / 10) % 11 = 0 - This is not correct.

I know that Java cannot technically perform modular operations, and part of me is thinking that I either need to somehow calculate the inverse, or use an array to store the possible output values.

2
javadivisionmodular-arithmetic
Err, 2 / 10 is 0. And 0 % 11 is 0. Why would it be 9? – JB Nizet
Because I'm doing it under mod 11. Not normal division. – Tony
What I've just done is: (2 * 10) % 11 = 9. Which seems to be giving me my correct answer. – Tony
Ah, of course. But multiplication and division are not exactly the same thing. You found the correct problem for your solution. – JB Nizet
@stivlo: the question is about inverting multiplication in modular arithmetic. Because 10 is its own inverse mod 11, multiplying by 10 and dividing by 10 has the same effect in modulo-11 arithmetic. That's why Tony happens to get the correct answer a few comments above. – Luke Woodward

2 Answers

5
votes

I think what you are looking for is how to find the multiplicative inverse of a number modulo 11.

10 is its own inverse modulo 11, so it isn't a particularly useful example. Instead, let's find the multiplicative inverse of 7 modulo 11.

To do this, we solve the equation 7a + 11b = 1 for a and b in integers. We use the Euclidean algorithm to find suitable values for a and b. In this case, we can take a = -3 and b = 2. We ignore the value of b, and take a ( = -3) to be the inverse of 7 modulo 11. In modulo-11 arithmetic, 7 times -3 is 1.

If we don't like negative numbers, we can take the inverse of 7 modulo 11 to be 8 ( = -3 + 11) instead.

So, instead of dividing by 7 modulo 11, we multiply by -3, or by 8. For example, in modulo-11 arithmetic, 9 / 7 = 9 * 8 = 72 = 6.

If you only ever have one modulus to work with (e.g. you only ever work modulo 11), it's probably better to calculate a table of multiplicative inverses modulo 11 beforehand and use that in your calculations.

1
votes

Not sure if this is what you intend, but...

public static int divmod(int dividend, int divisor, int mod) {
    if (dividend >= divisor)
        return (dividend / divisor) % mod;
    return mod - dividend;
}

Testing it:

divmod(9, 1, 11)  // returns 9
divmod(2, 10, 11) // returns 9