Main content

## Computer science

### 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 EquationLHS = (A + B) mod C

LHS = (

LHS =

LHS = (

**14 + 17**) mod 5LHS =

**31**mod 5**LHS = 1**RHS = (A mod C + B mod C) mod C

RHS = (

RHS = (

RHS = (

**14 mod 5 + 17 mod 5**) mod 5RHS = (

**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

We must show 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?

- "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...(13 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(17 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.(5 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 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) - I think I'm taking an L here(2 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)

- 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) - can you prove for subtraction because the answers may come negative(1 vote)