Modular Inverse

In order to be able to do modular division, we need to calculate the modular multiplicative inverse. In this video I introduce the additive inverse and the multiplicative inverse. Then I talk about how to use the mutiplicative inverse to do modular division.

It’s a bit unexpected, but it makes sense once you’ve got it.

Watch the video and then answer the questions below.

Eight-minute video

You can also view this video on YouTube

Key Points

Additive Inverse

• The additive inverse of a number is what you need to add to get 0.
• Usually, the additive inverse of a number a is -a, because a + (-a) = 0
• Under a modulus of n, the additive inverse of a number a is -a mod n

Multiplicative Inverse

• The multiplicative inverse of a number is what you need to multiply by to get 1.
• The multiplicative inverse of a is written as a-1
• Usually, for a number a this is 1/a, because a * 1/a = 1
• Under a modulus however, this will be whatever number you multiply by to get 1, after finding the modulus.
• The modular multiplicative inverse is only defined if the divisor and the modulus are coprime

Modular Division

• Instead of dividing by a number, we can multiply by its inverse: a/b = a*b-1
• Usually, to do 4/4 we could instead do 4(1/4), or 4 * 4-1
• However, under modulus, we must instead multiply by the modular multiplicative inverse.

Questions

1. Check your understanding

1. Additive Inverse

What is the additive inverse of:

1. 8
2. -1
3. 2n

Check Answers

2. Modular Additive Inverse

What is the additive inverse (modulo 5) of:

1. 4
2. 2
3. 0

Check Answers

3. Multiplicative Inverse

What is the multiplicative inverse of the following: (give your answers in decimal)

1. 2
2. -1
3. 20

4. Modular Multiplicative Inverse

Find the modular inverse of the following:

1. 4 (mod 11)
2. 3 (mod 7)
3. 5 (mod 9)

Is there a modular inverse of the following?

1. 7 (mod 11)?
2. 6 (mod 9)?
3. 9 (mod 12)?

Check Answers

2. Additive Inverse Function

Write a function in Java int additiveInverse(int a, int n) that returns the additive inverse of the number a, modulo n.

Summary

In this section we have learned how to find the additive and multipliative inverse under modulus, and use this to do modular division.

• You should be able to find the additive and multiplicative inverses of a number, including in modular arithmetic.
• You should know when the multiplicative inverse is defined in modular arithmetic.
• You should be able to do division in modular arithmetic.

Now you can move on to the modular arithmetic challenges.

Improve this page