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

(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
Зареждане