(A * B) mod C = (A mod C * B mod C) mod C
证明：
A = C * Q1 + R1 where 0 ≤ R1 < C and Q1 is some integer. A mod C = R1
B = C * Q2 + R2 where 0 ≤ R2 < C and Q2 is some integer. 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
得到最后一步， 设置 V = $(C * Q1 * Q2 + Q1 * R2 + Q2 * R1) $
那么显然 V倍的C % C 肯定 = 0 ； => LHS MOD C = (R1*R2) MOD C
∵ R_1 = A % C , R_2 = B % C
∴(A * B) mod C = (A % C * B %C) % C
作业：
试证明
(A + B) mod C = ？
(A / B) mod C = ?
参考：