主要内容
模的乘法
让我们探索模运算的乘法属性:
(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
LHS= 等式的左边
LHS= 等式的右边
LHS = (A * B) mod C
LHS = (4 * 7) mod 6
LHS = 28 mod 6
LHS = 4
RHS = (A mod C * B mod C) mod C
RHS = (4 mod 6 * 7 mod 6) mod 6
RHS = (4 * 1) mod 6
RHS = 4 mod 6
RHS = 4
LHS = RHS = 4
证明模运算的乘法属性
我们将证明 (A * B) mod C = (A mod C * B mod C) mod C
我们必须证明 LHS = RHS
根据 商余理论 我们可以将 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
LHS = (A * B) mod C
LHS = ((C * Q1 + R1 ) * (C * Q2 + R2) ) mod C
LHS = (C * C * Q1 * Q2 + C * Q1 * R2 + C * Q2 * R1 + R1 * R 2 ) mod C
LHS = (C * (C * Q1 * Q2 + Q1 * R2 + Q2 * R1) + R1 * R 2 ) mod C
我们可以利用mod C消除C的倍数
LHS = (R1 * R2) mod C
接着让我们继续 RHS
RHS = (A mod C * B mod C) mod C
RHS = (R1 * R2 ) mod C
因此 RHS = LHS
LHS = RHS = (R1 * R2 ) mod C