Addition of and Subtraction of Modulo Arithmetic:https://www.youtube.com/embed/E8SaCy-kmYU

Modular Multiplication by Khan Academy

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=6Let’s verify: (A * B) mod C = (A mod C * Bmod C) mod CLHS= Left Hand Side of the EquationRHS= Right Hand Side of the EquationLHS = (A * B) mod CLHS = (4 * 7) mod 6LHS = 28 mod 6LHS = 4RHS = (Amod C * Bmod C) mod CRHS = (4 mod 6 * 7 mod 6) mod 6RHS = (4 * 1) mod 6RHS = 4 mod 6RHS = 4LHS = RHS = 4

Proof for Modular Multiplication

We will prove that (A * B) mod C = (A mod C * B mod C) mod CWe must show that LHS = RHSFrom 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 = R1B = C * Q2 + R2 where 0 ≤ R2 < C and Q2 is some integer. B mod C = R2LHS = (A * B) mod CLHS = ((C * Q1 + R1 ) * (C * Q2 + R2) ) mod CLHS = (C * C * Q1 * Q2 + C * Q1 * R2 + C * Q2 * R1 + R1 * R 2 )  mod CLHS = (C * (C * Q1 * Q2 + Q1 * R2 + Q2 * R1)  + R1 * R 2 )  mod CWe can eliminate the multiples of C when we take the mod CLHS = (R1 * R2) mod CNext let’s do the RHSRHS = (A mod C * B mod C) mod CRHS = (R1 * R2 ) mod CTherefore RHS = LHSLHS = RHS = (R1 * R2 ) mod C