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