If you're seeing this message, it means we're having trouble loading external resources on our website.

If you're behind a web filter, please make sure that the domains *.kastatic.org and *.kasandbox.org are unblocked.

Main content

Modular inverses

What is an inverse?

Recall that a number multiplied by its inverse equals 1. From basic arithmetic we know that:
  • The inverse of a number A is 1/A since A * 1/A = 1 (e.g. the inverse of 5 is 1/5)
  • All real numbers other than 0 have an inverse
  • Multiplying a number by the inverse of A is equivalent to dividing by A (e.g. 10/5 is the same as 10* 1/5)

What is a modular inverse?

In modular arithmetic we do not have a division operation. However, we do have modular inverses.
  • The modular inverse of A (mod C) is A^-1
  • (A * A^-1) ≡ 1 (mod C) or equivalently (A * A^-1) mod C = 1
  • Only the numbers coprime to C (numbers that share no prime factors with C) have a modular inverse (mod C)

How to find a modular inverse

A naive method of finding a modular inverse for A (mod C) is:
step 1. Calculate A * B mod C for B values 0 through C-1
step 2. The modular inverse of A mod C is the B value that makes A * B mod C = 1
Note that the term B mod C can only have an integer value 0 through C-1, so testing larger values for B is redundant.

Example: A=3, C=7

Step 1. Calculate A * B mod C for B values 0 through C-1

3 * 0 ≡ 0 (mod 7)
3 * 1 ≡ 3 (mod 7)
3 * 2 ≡ 6 (mod 7)
3 * 3 ≡ 9 ≡ 2 (mod 7)
3 * 4 ≡ 12 ≡ 5 (mod 7)
3 * 5 ≡ 15 (mod 7) ≡ 1 (mod 7)   <------ ​FOUND INVERSE!
3 * 6 ≡ 18 (mod 7) ≡ 4 (mod 7)

Step 2. The modular inverse of A mod C is the B value that makes A * B mod C = 1

5 is the modular inverse of 3 mod 7 since 5*3 mod 7 = 1
Simple!
Let's do one more example where we don't find an inverse.

Example: A=2 C=6

Step 1. Calculate A * B mod C for B values 0 through C-1

2 * 0 ≡ 0 (mod 6)
2 * 1 ≡ 2 (mod 6)
2 * 2 ≡ 4 (mod 6)
2 * 3 ≡ 6 ≡ 0 (mod 6)
2 * 4 ≡ 8 ≡ 2 (mod 6)
2 * 5 ≡ 10 ≡ 4 (mod 6)

Step 2. The modular inverse of A mod C is the B value that makes A * B mod C = 1

No value of B makes A * B mod C = 1. Therefore, A has no modular inverse (mod 6).
This is because 2 is not coprime to 6 (they share the prime factor 2).

This method seems slow...

There is a much faster method for finding the inverse of A (mod C) that we will discuss in the next articles on the Extended Euclidean Algorithm.

Want to join the conversation?

  • female robot grace style avatar for user gunwati.rules
    Why is it that A has to be coprime to C to have a modular inverse?
    (25 votes)
    Default Khan Academy avatar avatar for user
  • leaf red style avatar for user Noble Mushtak
    Wait, I thought you could divide by any number in modular arithmetic as long as the number inside the modulus was relatively prime to the number you were dividing by. Do you always have to use modular inverses?

    I will find the faster method before Brit Cruise posts it up...
    EDIT:
    a mod b
    a^2 mod b
    a^3 mod b
    ...
    Eventually, one of these expressdions will get to 1. If b is prime, then a^(b-1) mod b will be congruent to 1.
    a^n mod b=1
    a^(n-1)*a mod b=1
    a^(n-1) mod b is the modular inverse of a mod b and if b is prime, a^(b-2) is the modular inverse of a mod b.

    That's as close as I got.

    This was edited just before the Extended Euclidean Algorithm was posted.
    (8 votes)
    Default Khan Academy avatar avatar for user
    • male robot hal style avatar for user Cameron
      Division doesn't exist in modular arithmetic. However, many of the things we can do with modular inverses act the same as or similar to division.

      e.g.
      if we have a * k ≡ b * k (mod C) where k is coprime to C we can eliminate the k from each side and say:
      a ≡ b (mod C)

      How did we eliminate k ?
      We know that k has an inverse mod C since k is coprime to C. (We don't need to know what the value of the inverse is. We just need to know an inverse exists.)
      So when we have a * k ≡ b * k (mod C) , we multiply both sides by k^-1
      a * k * k^-1 ≡ b * k * k^-1 (mod C)
      but since k * k^-1 = 1 we have
      a * 1 ≡ b * 1 (mod C)
      a ≡ b (mod C)

      So as you can see, we are not dividing, but instead using modular inverses. The end result looks like we are dividing and intuitively what we are doing is similar, but is important to note that we don't have division in modular arithmetic, but in some cases we do have inverses.

      Hope this makes sense
      (14 votes)
  • male robot hal style avatar for user Tjon Lichy
    Wait a second! There is a much faster method for finding the inverse of A (mod C) that we will discuss in the next articles on the Extended Euclidean Algorithm. First, let's do some exercises! But where are the exercises? The next stop is "The Euclidean Algorithm".
    (12 votes)
    Default Khan Academy avatar avatar for user
  • piceratops ultimate style avatar for user Chris Torrence
    Did the Extended Euclidean Algorithm articles ever get published? These modular arithmetic articles have been fantastic, and I'm really looking forward to the next articles!
    (10 votes)
    Default Khan Academy avatar avatar for user
  • winston default style avatar for user AmiNe Sos
    Cameron said there is no division in modular arithmetic. But my problem sais:
    Solve: 11x ≡ 11 mod33
    Now the only way I can think of it is to devide by 11 both sides plus the mod
    So we get x ≡ 1 mod3
    And its correct! But if theres no division how would I solve it??
    Please clarify to me, thanks in advance
    (2 votes)
    Default Khan Academy avatar avatar for user
    • male robot hal style avatar for user Cameron
      There is no division in modular arithmetic.

      Suppose we had an equation like:
      A * x ≡ B mod C

      **If A was coprime to C**
      i.e. gcd(A,C)=1
      To solve for x we would multiply both sides by the modular inverse of A mod C

      A * A^-1 * x ≡ B * A^-1 mod C
      But A * A^-1 mod C = 1
      1 * x ≡ B * A^-1 mod C
      And 1 * x mod C = x
      x ≡ B * A^-1 mod C

      e.g.
      5 * x ≡ 2 mod 14
      5 is coprime with 14, so 5 has an inverse mod 14
      5 * 5^-1 * x ≡ 2 * 5^-1 mod 14
      1 * x ≡ 2 * 5^-1 mod 14
      x ≡ 2 * 5^-1 mod 14
      5^-1 mod 14 is 3, since 3 * 5 mod 14 = 15 mod 14 = 1
      x ≡ 2 * 3 mod 14
      x ≡ 6 mod 14


      **But what do we do if A is NOT coprime to C**
      i.e. gcd(A,C) != 1 ?
      To solve for x, we need to convert the expression to an equivalent form
      A * x ≡ B mod C
      is equivalent to:
      A * x = K * C + B where K is an integer
      This is just a regular equation, so we can use divide here.
      If A,B and C are ALL divisible by D then we can divide both sides of the equation to get:
      (A/D) * x = K * (C/D) + (B/D) where K is an integer
      Note that:(A/D) , (C/D), and (B/D) will all be integers
      We can then convert this new equation into a congruence to get:
      (A/D) * x ≡ (B/D) mod (C/D)

      So, it only seems like we can divide by D when A,B and C are ALL divisible by D
      (but it isn't really division, it only looks similar to division)

      But you need to be careful !! If you solve for x now, you will have an answer mod (C/D)
      You will need to find all the possible values where 0 <= x < C to be able to express your answer mod C

      e.g.
      12 * x ≡ 15 mod 45
      is equivalent to:
      12 * x = K * 45 + 15
      Divide both sides by 3
      4 * x = K * 15 + 5
      is equivalent to:
      4 * x ≡ 5 mod 15
      This new expression can then be solved using the method for A coprime to C
      4 * x ≡ 5 mod 15
      4 * 4^-1 * x ≡ 5 * 4^-1 mod 15
      4^-1 mod 15 is 4 since 4 * 4 mod 15 = 16 mod 15 = 1
      x ≡ 5 * 4 mod 15
      x ≡ 20 mod 15
      x ≡ 5 mod 15
      (But this answer is mod 15, we need our answer to be mod 45)
      our expression is equivalent to x = K * 15 + 5 where K is an integer
      So the possible values of 0 <= x < 45 are:
      5,20,35
      So our answer is:
      x ≡ 5, 20, or 35 mod 45

      So, as far as 11 * x ≡ 11 mod 33 goes, you can obtain x ≡ 1 mod 3 from it.
      This only works because all of the terms are divisible by 11. Again, what's happening is not really division (it only seems similar).
      Additionally, the solution needs to be converted to mod 33.
      i.e. x ≡ 1,4,7,10,13,16,19,22,25,28, or 31 mod 33

      Hope this makes sense
      (3 votes)
  • leaf green style avatar for user Armin Roüshan
    I want to know how can you show if a number has an inverse or not.
    Example: show the number 6 does not have a multiplication inverse modulo 15.
    (2 votes)
    Default Khan Academy avatar avatar for user
  • leaf green style avatar for user bassam.ahmed32
    how can i proof that if: k =a*b mod n
    then
    k^-1 = a^-1 * b^-1 mod n
    (2 votes)
    Default Khan Academy avatar avatar for user
    • male robot hal style avatar for user Cameron
      Here's a big hint:

      Start from this congruence
      K * K^-1 ≡ 1 (mod N)
      Then try to reach this congruence:
      K^-1 ≡ A^-1 * B^-1 (mod N)

      You will need to use this: K ≡ A * B (mod N)
      and the property that: X * X^-1 ≡ 1 (mod N)

      Good Luck
      (2 votes)
  • blobby green style avatar for user azmatshah98
    if ab≡1 mod n, and b<n, how do I prove that b is unique.
    (2 votes)
    Default Khan Academy avatar avatar for user
    • male robot hal style avatar for user Cameron
      Typically, when you have some thing with some property and you want to prove it is unique, you do the following:
      Suppose that both b and c have that property.
      Show that b = c.
      This shows that everything that has that property is b, i.e. there isn't anything with that property that is not b.


      This case is similar:
      - we would assume that both b and c have the same property i.e. both b and c are inverses of a (mod n)
      - we need to show that b ≡ c (mod n)

      Proof:
      Suppose b and c are inverses of a (mod n)
      Since b is an inverse of a (mod n):
      a * b ≡ 1 (mod n)
      Since c is an inverse of a (mod n):
      a * c ≡ 1 (mod n)

      a * b ≡ 1 (mod n)
      subsitute (a * c) into right hand side
      a * b ≡ a * c (mod n)
      multiply both sides by a^-1
      a * a^-1 * b ≡ a * a^-1 * c (mod n)
      1 * b ≡ 1 * c (mod n)
      b ≡ c (mod n)


      Hope this makes sense
      (2 votes)
  • leaf red style avatar for user Noble Mushtak
    Does this program correctly compute modular inverses with the Trial and Error method above?
    http://www.khanacademy.org/cs/find-the-modular-inverse-with-trial-and-error-and-computer-computational-power/1832730911
    (2 votes)
    Default Khan Academy avatar avatar for user
  • blobby green style avatar for user felipe.rodrigo.g
    I don't undertake how is it that (A * A^-1) ≡ 1 (mod C).
    Your website is awesome! It is helping me a lot
    (2 votes)
    Default Khan Academy avatar avatar for user