1

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.

Improve this question
7
  • 7
    Err, 2 / 10 is 0. And 0 % 11 is 0. Why would it be 9? Commented Oct 22, 2011 at 16:13
  • 3
    Because I'm doing it under mod 11. Not normal division. Commented Oct 22, 2011 at 16:17
  • What I've just done is: (2 * 10) % 11 = 9. Which seems to be giving me my correct answer. Commented Oct 22, 2011 at 16:18
  • Ah, of course. But multiplication and division are not exactly the same thing. You found the correct problem for your solution. Commented Oct 22, 2011 at 16:23
  • 1
    @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. Commented Oct 22, 2011 at 19:48

2 Answers 2

Reset to default
5

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.

Improve this answer
Sign up to request clarification or add additional context in comments.

5 Comments

Thanks for that Luke, I had a suspicion that's what I was going to have to do. Do you have any advice on generating such a table? I'm guessing I need a multi-dimensional array?
I don't see why you'd need a multidimensional array. If you only ever work modulo 11, calculate of the inverses of 1 to 10 modulo 11 and put them in a 1-dimensional array. If you're working with lots of moduli, or any large moduli, a table won't be such a good idea.
Thanks Luke, I was getting a bit confused with what I was trying to do (it's still quite early for me) :). I've now built an inverse table using an array, and now everything is working as planned. Thanks for your help!!
Luke, you've been a massive help, and I was wondering if I could ask of your help for a final time. Simply, I need a way in Java of it outputting 7, when I put in y = -4 % 11. Any suggestions?
@Tony: one possible expression that handles negative numbers as well as positive numbers is ((y % 11) + 11) % 11.
1

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
Improve this answer

2 Comments

Thanks Óscar, this works for some number pairs, but fails for others.
Give me a set of numbers for testing, specially the ones that fail, and I'll see what I can do to help you

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.