Java modular division

Question

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.

Answer 1

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.

Answer 2

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