Main content
Computer science theory
Course: Computer science theory > Unit 2
Lesson 5: Modular arithmetic- What is modular arithmetic?
- Modulo operator
- Modulo Challenge
- Congruence modulo
- Congruence relation
- Equivalence relations
- The quotient remainder theorem
- Modular addition and subtraction
- Modular addition
- Modulo Challenge (Addition and Subtraction)
- Modular multiplication
- Modular multiplication
- Modular exponentiation
- Fast modular exponentiation
- Fast Modular Exponentiation
- Modular inverses
- The Euclidean Algorithm
© 2023 Khan AcademyTerms of usePrivacy PolicyCookie Notice
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 = 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
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
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).
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
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
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
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
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?
"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)
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)
- So, will modular subtraction proof be written here?(10 votes)
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)
- 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)- 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)
(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)- 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)
- I think I'm taking an L here(4 votes)
- 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) - Ans for a=8 b=9 c=7
(a-b)%c=-1 by ur logic(1 vote)- 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)
I don't get any of this; what is this I'm totally lost :( :?(0 votes)
I know that this question has been posted a year ago, but what part is confusing?(3 votes)
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)- 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)
