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 multiplication

Let's explore the multiplication property of modular arithmetic:

(A * B) mod C = (A mod C * B mod C) mod C

Example for Multiplication:

Let A=4, B=7, C=6
Let's verify: (A * B) mod C = (A mod C * B mod C) mod C
LHS= Left Hand Side of the Equation
RHS= Right Hand Side of the Equation
LHS = (A * B) mod C
LHS = (4 * 7) mod 6
LHS = 28 mod 6
LHS = 4
RHS = (A mod C * B mod C) mod C
RHS = (4 mod 6 * 7 mod 6) mod 6
RHS = (4 * 1) mod 6
RHS = 4 mod 6
RHS = 4
LHS = RHS = 4

Proof for Modular Multiplication

We will prove that (A * B) mod C = (A mod C * B mod C) mod C
We must show that LHS = RHS
From the quotient remainder theorem we can write A and B as:
A = C * Q1 + R1 where 0 ≤ R1 < C and Q1 is some integer. A mod C = R1
B = C * Q2 + R2 where 0 ≤ R2 < C and Q2 is some integer. B mod C = R2
LHS = (A * B) mod C
LHS = ((C * Q1 + R1 ) * (C * Q2 + R2) ) mod C
LHS = (C * C * Q1 * Q2 + C * Q1 * R2 + C * Q2 * R1 + R1 * R 2 )  mod C
LHS = (C * (C * Q1 * Q2 + Q1 * R2 + Q2 * R1)  + R1 * R 2 )  mod C
We can eliminate the multiples of C when we take the mod C
LHS = (R1 * R2) mod C
Next let's do the RHS
RHS = (A mod C * B mod C) mod C
RHS = (R1 * R2 ) mod C
Therefore RHS = LHS
LHS = RHS = (R1 * R2 ) mod C

Want to join the conversation?

  • leaf blue style avatar for user Matt
    I'm a little confused as to why you would choose to do (A mod C * B mod C) mod C, over (A*B) mod C. (And likewise for addition or subtraction) The A*B route seems much simpler...?
    (14 votes)
    Default Khan Academy avatar avatar for user
  • primosaur ultimate style avatar for user Jackson dC
    Is there an intuitive explanation for modular multiplication (something involving clocks) like there is for modular addition?
    (12 votes)
    Default Khan Academy avatar avatar for user
    • male robot hal style avatar for user Cameron
      Here's an analogy that might work for you.

      Suppose we have:
      - a cylinder, which we can just barely wrap a rope of length C around
      - a rope, that we have marked every A units

      Suppose our rope has B markings from its start. (The rope has length A * B)

      We nail the rope to our cylinder and we wrap it clockwise around our cylinder.

      (A * B) mod C tells us: how much rope to we need to go clockwise from the nail to reach the end of the rope (we don't care about the length of rope that completely wraps around the cylinder)

      It is equivalent to the expression:
      (A mod C * B mod C) mod C

      A mod C tells us:
      How much further (clockwise) a segment of length A will be from the previous segment after wrapping it around the cylinder.

      We use B mod C, because if we wrap C segments of length A around the cylinder, the length (A * C) will be evenly divisible by C and we would be just back at the nail i.e. B mod C is the number of segments that actually contribute to the end of the rope being further away from the nail

      I would also suggest looking at the "Intuition Behind Modular Addition" section in the modular addition article. Multiplication is essentially just repeated addition.

      Hope this makes sense
      (10 votes)
  • male robot donald style avatar for user Ishan Deo
    Suppose a question is given: X = 12 * 53 mod 32
    Now, does it mean X = (12 * 53) mod 32 or X = 12 * (53 mod 32) ?
    (5 votes)
    Default Khan Academy avatar avatar for user
    • male robot hal style avatar for user Cameron
      Unfortunately, it can be used to be mean either.

      Hopefully, the context that it is being used in should make it obvious which is meant. If the context does not make it obvious what is meant then the writer should use adequate brackets to make it obvious.

      That, being said, most often it will be used to mean: X = (12 * 53) mod 32, but the other usage is not unheard of.
      (11 votes)
  • leaf green style avatar for user codysgotgame
    Just thinking out loud and seeing possibilities: Is there a practical use for cascading Modulus?

    (((29 mod 17) mod 7) mod 3) = x
    where
    29 mod 17 = 12
    12 mod 7 = 5
    5 mod 3 = 2
    x = 2
    (2 votes)
    Default Khan Academy avatar avatar for user
    • mr pink red style avatar for user Varun
      You could use it to give yourself some more time before people catch on to your RSA, but not much else. And with RSA, you already have a few hundred years anyway. You could also use it to make programmers go hysteric by seeing 500 nested parentheses.
      (3 votes)
  • blobby green style avatar for user Schmichael Chen
    "LHS = (C * (C * Q1 * Q2 + Q1 * R2 + Q2 * R1) + R1 * R 2 ) mod C

    We can eliminate the multiples of C when we take the mod C

    LHS = (R1 * R2) mod C"

    Could someone please help explain how the top line and the bottom line are identical?

    "LHS = (C * (C * Q1 * Q2 + Q1 * R2 + Q2 * R1) + R1 * R 2 ) mod C" is supposed to give us R1 * R2, not (R1 * R2) mod C. There is something I'm missing here.

    I can understand how we end up with

    "RHS = (A mod C * B mod C) mod C
    RHS = (R1 * R2 ) mod C"

    Thanks a lot.
    (2 votes)
    Default Khan Academy avatar avatar for user
  • blobby green style avatar for user gabi.yarmish
    In the proof of the RHS how did you get from RHS = (A mod C * B mod C) mod C which is
    (R1 mod C * R2 mod C) mod C
    to the next step
    (R1 * R2 ) mod C

    Isn't that what you need to prove?
    (1 vote)
    Default Khan Academy avatar avatar for user
    • male robot hal style avatar for user Cameron
      Explaining the proof
      RHS = (A mod C * B mod C) mod C
      A mod C = R1
      B mod C = R2
      substitute these values into the above to get:
      RHS = (R1 * R2) mod C

      Why (R1 * R2) mod C = (R1 mod C * R2 mod C) mod C isn't enough

      We could say the following:
      RHS = (A mod C * B mod C) mod C
      RHS = (R1 * R2) mod C (since A mod C=R1 and B mod C=R2)
      RHS= (R1 mod C* R2 mod C) mod C
      (since for any integer X< C, X mod C = X, which is the case for R1 and R2)

      This would give us: (R1 * R2) mod C = (R1 mod C* R2 mod C) mod C
      (by equating the last two expressions above)

      Is showing that:
      (R1 * R2) mod C = (R1 mod C* R2 mod C) mod C
      the same as showing that:
      (A * B) mod C = (A mod C * B mod C) mod C ?

      No.
      Here's why:
      A, B, C are arbitrarily chosen integers.
      On the other hand R1,R2 must both be less than C.
      If A or B >=C the statements are not equivalent.

      Hope this makes sense
      (4 votes)
  • blobby green style avatar for user Mitch Raful
    Can someone show me the algebraic hocus pocus that gets us from the first line to the second line?

    LHS = ((C * Q1 + R1 ) * (C * Q2 + R2) ) mod C
    LHS = (C * C * Q1 * Q2 + C * Q1 * R2 + C * Q2 * R1 + R1 * R 2 ) mod C
    (2 votes)
    Default Khan Academy avatar avatar for user
    • male robot hal style avatar for user Cameron
      No magic involved. It's just multiplying the stuff out in brackets.
      Every term in the first set of brackets gets multiplied by every term in the second set of brackets.
      (Some schools teach a FOIL method for multiplying binomials)

      In general:
      (a+b) * (c+d) = ac + ad + bc + bd

      So, in the the first line we have:
      a = C * Q1
      b = R1
      c = C * Q2
      d = R2

      which gives us:
      (a+b) * (c+d) = ((C * Q1) + (R1) ) * ((C * Q2) + (R2))
      (a+b) * (c+d) = (C * Q1) * (C * Q2) + (C * Q1) * (R2) + (R1) * (C * Q2) + (R1) * (R2)
      removing brackets and rearranging terms (to make it more obvious which are multiples of C) we get:
      (a+b) * (c+d) = C * C * Q1 * Q2 + C * Q1 * R2 + C * Q2 * R1 + R1 * R2

      Hope this makes sense
      (2 votes)
  • blobby green style avatar for user vikash2695
    What about Modulo Division?
    (3 votes)
    Default Khan Academy avatar avatar for user
    • blobby green style avatar for user dbrianwalton
      This is actually a great question, and I'm surprised it hasn't been commented on (that I can see). First, I want to say something about subtraction so that we have a decent analogy to use.

      Subtraction is the inverse operation for addition. One cool thing about the number system is that we can use additive inverses in place of subtraction. In ordinary arithmetic, we would say 4 - 7 = 4 + -7 which has a value -3. However, in modular arithmetic, we don't see those negative values. Instead the additive inverse of a number is that modulus such that when you add it to the number you get 0. (That's really the same idea: -4 is the inverse of 4 because -4 + 4 = 0.) For example, because 2+3=0 mod 5, 3 is the additive inverse of 2 (and vice versa). This means that (x-2) mod 5 and (x+3) mod 5 are going to always be the same.

      Now, about division. The analog for an additive inverse is the multiplicative inverse. In ordinary arithmetic, you learned about that as being the reciprocal. We don't have fractions in this arithmetic. If you look at a multiplication table for modular arithmetic, you will see that sometimes we have a value 1 as the product. For example, 2*3 mod 5 = 1. This means that 2 and 3 are also multiplicative inverses of one another mod 5.

      Division itself is not something that is defined. But we might have a question like, "Twice a number equals 1 mod 5" or 2x=3 mod 5. In ordinary arithmetic, we would divide by 2. That doesn't exist. But we do have a multiplicative inverse, and we can multiply both sides by 3. This gives a new equation 3*2x = 3*3 mod 5 or x = 4 mod 5.
      (0 votes)
  • leafers ultimate style avatar for user Shreyas Pai
    Is there modular division?
    (2 votes)
    Default Khan Academy avatar avatar for user
  • piceratops ultimate style avatar for user Dragonix
    I am wondering what this has too do with cryptography. Isn't it math?
    (1 vote)
    Default Khan Academy avatar avatar for user