Умножение по модул

Да разгледаме свойството умножение в модулната аритметика:

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

Нека A=4, B=7, C=6

Нека проверим: (A * B) mod C = (A mod C * B mod C) mod C

ЛСУ= Лява Страна на Уравнението

ДСУ= Дясна Страна на Уравнението

ЛСУ = (A * B) mod C

ЛСУ = (4 * 7) mod 6

ЛСУ = 28 mod 6

ЛСУ = 4

ДСУ = (A mod C * B mod C) mod C

ДСУ = (4 mod 6 * 7 mod 6) mod 6

ДСУ = (4 * 1) mod 6

ДСУ = 4 mod 6

ДСУ = 4

ЛСУ = ДСУ = 4

Ще докажем, че (A * B) mod C = (A mod C * B mod C) mod C

Трябва да покажем, че ЛСУ = ДСУ

От Теоремата за частно и остатък можем да запишем А и В като:

A = C * Q1 + R1 , където 0 ≤ R1 < C и Q1 е някое число. A mod C = R1

B = C * Q2 + R2 , където 0 ≤ R2 < C и Q2 е някое число. B mod C = R2

ЛСУ = (A * B) mod C

ЛСУ = ((C * Q1 + R1 ) * (C * Q2 + R2) ) mod C

ЛСУ = (C * C * Q1 * Q2 + C * Q1 * R2 + C * Q2 * R1 + R1 * R 2 ) mod C

ЛСУ = (C * (C * Q1 * Q2 + Q1 * R2 + Q2 * R1) + R1 * R 2 ) mod C

Можем да елимираме множеителите на С, като вземем mod C

ЛСУ = (R1 * R2) mod C

Сега да изчислим ДСУ

ДСУ = (A mod C * B mod C) mod C

ДСУ = (R1 * R2 ) mod C

Следователно ДСУ = ЛСУ

ЛСУ = ДСУ = (R1 * R2 ) mod C

Сортирай по:

Все още няма публикации.