# 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 CLHS =

**(4 * 7)**mod 6LHS =

**28**mod 6LHS =

**4**RHS = (

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

**4 mod 6*****7 mod 6**) mod 6RHS = (

**4 * 1**) mod 6RHS =

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