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 addition and subtraction

Let's explore the addition property of modular arithmetic:

(A + B) mod C = (A mod C + B mod C) mod C

Example:

Let A=14, B=17, C=5
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 = (14 + 17) mod 5
LHS = 31 mod 5
LHS = 1
RHS = (A mod C + B mod C) mod C
RHS = (14 mod 5 + 17 mod 5) mod 5
RHS = (4 + 2) mod 5
RHS = 1
LHS = RHS = 1

Intuition Behind Modular Addition

Observe the figure below. If we want to calculate 12+9 mod 7 we can easily go around the modular circle for a sequence of 12+9 steps clockwise (as shown in the bottom left circle).
mod
We can take a shortcut by observing that every 7 steps we end up in the same position on the modular circle. These complete loops around the modular circle don’t contribute to our final position. We ignore these complete loops around the circle by calculating each number mod 7 (as shown in the two upper modular circles). This will give us the number of clockwise steps, relative to 0, that contributed to each of their final positions around the modular circle.
Now, we only have to go around the circle clockwise the total of the number of steps that contributed to each of numbers final position (as shown in the bottom right modular circle). This method applies, in general, to any two integers and any modular circle.

Proof for Modular Addition

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
(A + B) = C * (Q1 + Q2) + R1+R2
LHS = (A + B) mod C
LHS = (C * (Q1 + Q2) + R1+ R2) mod C
We can eliminate the multiples of C when we take the mod C
LHS = (R1 + R2) mod C
RHS = (A mod C + B mod C) mod C
RHS = (R1 + R2) mod C
LHS=RHS= (R1 + R2) mod C

Modular Subtraction

A very similar proof holds for modular subtraction

(A - B) mod C = (A mod C - B mod C) mod C

Want to join the conversation?

  • blobby green style avatar for user JohnBltz
    "We can eliminate the multiples of C when we take the mod C"

    What does this mean? It feels like half the equation (C, Q1 and Q2) is just dropped and I have no idea why...
    (15 votes)
    Default Khan Academy avatar avatar for user
    • male robot hal style avatar for user Cameron
      This follows from the conclusion in the first lesson:
      "If we have A mod B and we increase A by a multiple of B, we will end up in the same spot i.e. A mod B = (A + K * B) mod B for any integer K."

      Thus when we have:
      LHS = (C * (Q1 + Q2) + R1+ R2) mod C
      we can dump the integer multiple of C
      LHS= (R1+R2) mod C

      Perhaps going through the proof a couple times while substituting in actual numbers will help.

      Hope this makes sense
      (19 votes)
  • blobby green style avatar for user Krors
    So, will modular subtraction proof be written here?
    (10 votes)
    Default Khan Academy avatar avatar for user
    • orange juice squid orange style avatar for user jmullercuber
      The only difference is that B is negative. If you were to think back to algebra, you can just substitue all Bs for -Bs and it would be just the same, piggybacking off the modular addition proof.
      Or, because the modular addition proof was defined for integers A and B, and you know an negative integer is just another integer, by messing with the domain the rule holds.
      (6 votes)
  • blobby green style avatar for user erharshkara
    but if a=9,b=6 c=4
    (a-b)%c=3
    whereas (a%c-b%c)%c=-1
    so then how can we say that that (A - B) mod C = (A mod C - B mod C) mod C
    (4 votes)
    Default Khan Academy avatar avatar for user
    • male robot hal style avatar for user Cameron
      a=9,b=6, c=4
      (a-b) mod c = (9-6) mod 4 = 3 mod 4 = 3
      (a mod c - b mod c) mod c = (9 mod 4 - 6 mod 4) mod 4 = (1 - 2) mod 4 = -1 mod 4 = 3
      Note: -1 mod 4 = 3 not -1. Negative remainders are not allowed.

      Be very wary of using the % function on your calculator or the computer to calculate mods. Most calculators and most calculators do not correctly calculate mods for negative numbers (the Python language is a rare exception that does calculates them correctly). This is due to technical reasons on how these functions are implemented in the hardware of computer processors (they use a hack that uses the existing integer division hardware).

      However, if you do use % function to calculate 'a mod c' and you get a negative result, you will get the correct result by adding 'c' to it.
      e.g. if you calculate -1 % 4 and get back -1, then add 4 to get 3 (the correct result)

      Hope this makes sense
      (8 votes)
  • duskpin ultimate style avatar for user May Lew
    (A + B) = C * (Q1 + Q2) + R1+R2
    (1)LHS = (A + B) mod C
    (2)LHS = (C * (Q1 + Q2) + R1+ R2) mod C
    (3)
    We can eliminate the multiples of C when we take the mod C
    LHS = (R1 + R2) mod C

    WHAT DOES (3) MEAN BY DETAIL?
    (2 votes)
    Default Khan Academy avatar avatar for user
    • male robot hal style avatar for user Cameron
      Here's what it means:
      If we are calculating X mod C, then:
      we can add multiples of C to X or subtract multiples of C from X and the result mod C will not change
      i.e. X mod C = (X+ K * C) mod C where K is an integer

      e.g. 5 mod 7 = ( 5 + 7 )mod 7 = (5 + 2 * 7) mod 7 = (5 - 29 * 7) mod 7 = (5 + 42 * 7) mod 7 = 5

      This is discussed in previous articles

      The contribution of the multiple of C mod 7 is 0.

      Why is this true ?

      From the quotient remainder theorem we have:
      X = Q * C + R , where 0 <= R < C
      Let's add an integer multiple of C to both sides of this equation
      i.e. let's add K * C where K is some integer
      X + K * C = Q * C + R + K * C
      Now we group the terms on the right hand side
      X + K * C = (Q + K) * C + R
      The result of adding integers Q + K is just another integer
      Let's call this new integer G
      The result of X + K * C is just another integer
      Let's call this new integer Y
      Y = G * C + R, where 0 <= R < C
      This is the exact form of the quotient remainder theorem !!
      Thus the remainder of Y divided by C is R
      But Y = X + K * C
      So the remainder of X + K * C divided by C is R.
      But this means than X and X + K * C have the same remainder R.

      So in the specific example
      (R1 + R2) mod C = (C * (Q1 + Q2) + R1+ R2) mod C
      because this is in the form
      X mod C = (X+ K * C) mod C

      Hope this makes sense
      (7 votes)
  • blobby green style avatar for user Mohammad Ali
    I think I'm taking an L here
    (4 votes)
    Default Khan Academy avatar avatar for user
  • blobby green style avatar for user Nick Kata
    I know that (x1 + x2 + x3 + ... + xn) mod D = (x1 mod D + x2 mod D + x3 mod D + ... + xn mod D) mod D (the proof is similar to multiplication x1 x2 .... xn mod D).

    But is the following property correct ?
    (x1 + x2 + x3 + ... + xn) mod D = (((((x1 mod D + x2) mod D + x3) mod D + x4) mod D + .... ) mod D + xn ) mod D.

    I think it is correct because for example (719 + 23 + 99) mod 10 = (((719 mod 10 + 23) mod 10) + 99) mod 10 = (((9 + 23)mod 10 + 99)mod 10 = (32 mod 10 + 99)mod10 = (2 + 99)mod10 = 101 mod 10 = 1

    Is there a proof for it ?
    Thanks
    (3 votes)
    Default Khan Academy avatar avatar for user
  • blobby green style avatar for user kanishkj34
    Ans for a=8 b=9 c=7
    (a-b)%c=-1 by ur logic
    (1 vote)
    Default Khan Academy avatar avatar for user
    • male robot hal style avatar for user Cameron
      That is incorrect.
      Be careful if you are using x % y on a calculator or computer to calculate x mod y.
      % may not give you the correct results if x is negative.

      (8-9) mod 7 = -1 mod 7 = 6
      (remember that x mod y will give a result between 0 and y-1 i.e. a negative result is not valid)

      Alternatively, we could calculate it as follows:
      (8 - 9) mod 7 = (8 mod 7 - 9 mod 7) mod 7 = (1 - 2) mod 7 = -1 mod 7 = 6

      Hope this makes sense
      (2 votes)
  • starky ultimate style avatar for user ROCKARMY650
    I don't get any of this; what is this I'm totally lost :( :?
    (0 votes)
    Default Khan Academy avatar avatar for user
  • spunky sam blue style avatar for user rajivkumarmarrapu
    Given a number N find the count of all ways such that (a + b + 2*c ) mod (x + y + 2*z) == 0 such that 1 < = a , b , c , x , y , z < = N
    (1 vote)
    Default Khan Academy avatar avatar for user
  • blobby green style avatar for user diomeryspantaleon21
    If a + b + c = -10a+b+c=−10a, plus, b, plus, c, equals, minus, 10 and x + y + z = -10x+y+z=−10x, plus, y, plus, z, equals, minus, 10,
    what is -6c - 6b + 6z + 6x + 6y - 6a−6c−6b+6z+6x+6y−6aminus, 6, c, minus, 6, b, plus, 6, z, plus, 6, x, plus, 6, y, minus, 6, a?
    (1 vote)
    Default Khan Academy avatar avatar for user