Addition, Subtraction and Multiplication of Modulo Arithemetic

Addition of and Subtraction of Modulo Arithmetic:

Modular Multiplication by Khan Academy

data-perseus-paragraph-index=”0″>

Let’s explore the multiplication property of modular arithmetic:

data-perseus-paragraph-index=”0″>

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

data-perseus-paragraph-index=”0″>

Example for Multiplication:

data-perseus-paragraph-index=”0″>

Let A=4, B=7, C=6

data-perseus-paragraph-index=”0″>

Let’s verify: (A * B) mod C = (A mod C * B mod C) mod C

data-perseus-paragraph-index=”0″>

LHS= Left Hand Side of the Equation

data-perseus-paragraph-index=”0″>

RHS= Right Hand Side of the Equation

data-perseus-paragraph-index=”0″>

LHS = (A * B) mod C

data-perseus-paragraph-index=”0″>

LHS = (4 * 7) mod 6

data-perseus-paragraph-index=”0″>

LHS = 28 mod 6

data-perseus-paragraph-index=”0″>

LHS = 4

data-perseus-paragraph-index=”0″>

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

data-perseus-paragraph-index=”0″>

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

data-perseus-paragraph-index=”0″>

RHS = (4 * 1) mod 6

data-perseus-paragraph-index=”0″>

RHS = 4 mod 6

data-perseus-paragraph-index=”0″>

RHS = 4

data-perseus-paragraph-index=”0″>

LHS = RHS = 4

data-perseus-paragraph-index=”0″>

Proof for Modular Multiplication

data-perseus-paragraph-index=”0″>

We will prove that (A * B) mod C = (A mod C * B mod C) mod C

data-perseus-paragraph-index=”0″>

We must show that LHS = RHS

data-perseus-paragraph-index=”0″>

From the quotient remainder theorem we can write A and B as:

data-perseus-paragraph-index=”0″>

A = C * Q1 + R1 where 0 ≤ R1 < C and Q1 is some integer. A mod C = R1

data-perseus-paragraph-index=”0″>

B = C * Q2 + R2 where 0 ≤ R2 < C and Q2 is some integer. B mod C = R2

data-perseus-paragraph-index=”0″>

LHS = (A * B) mod C

data-perseus-paragraph-index=”0″>

LHS = ((C * Q1 + R1 ) * (C * Q2 + R2) ) mod C

data-perseus-paragraph-index=”0″>

LHS = (C * C * Q1 * Q2 + C * Q1 * R2 + C * Q2 * R1 + R1 * R 2 ) mod C

data-perseus-paragraph-index=”0″>

LHS = (C * (C * Q1 * Q2 + Q1 * R2 + Q2 * R1) + R1 * R 2 ) mod C

data-perseus-paragraph-index=”0″>

We can eliminate the multiples of C when we take the mod C

data-perseus-paragraph-index=”0″>

LHS = (R1 * R2) mod C

data-perseus-paragraph-index=”1″>

Next let’s do the RHS

data-perseus-paragraph-index=”0″>

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

data-perseus-paragraph-index=”0″>

RHS = (R1 * R2 ) mod C

data-perseus-paragraph-index=”1″>

Therefore RHS = LHS

data-perseus-paragraph-index=”2″>

LHS = RHS = (R1 * R2 ) mod C

Read our disclaimer.

AD: Take Free online baptism course: Preachi.com

SS1 First Term Mathematics Senior Secondary School

Addition, Subtraction and Multiplication of Modulo Arithemetic

Addition of and Subtraction of Modulo Arithmetic:

Modular Multiplication by Khan Academy

Let’s explore the multiplication property of modular arithmetic:

Example for Multiplication:

Proof for Modular Multiplication

Share this:

Related

Modal title