Java modular division
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
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.