Основное содержание

Информатика

Урок 5: Модульная арифметика

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

(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 и B можно записать в виде:

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 + Q2) + R1+ 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

Мы можем опустить кратные C числа при делении по модулю C

ЛЧ = (R1 + R2) mod C

Теперь рассмотрим ПЧ

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

ПЧ = (R1 * R2 ) mod C

Следовательно, ЛЧ=ПЧ

ЛЧ = ПЧ = (R1 * R2 ) mod C

Сортировать по: