If you're seeing this message, it means we're having trouble loading external resources on our website.

如果你被网页过滤器挡住,请确保域名*.kastatic.org*.kasandbox.org 没有被阻止.

主要内容

模的加、减法

让我们探索模运算的 加法属性

(A + B) mod C = (A mod C + B mod C) mod C

示例:

A=14, B=17, C=5
让我们证明:(A + B) mod C = (A mod C + B mod C) mod C
LHS = 等式左边
RHS = 等式右边
LHS = (A + B) mod C
LHS = (14 + 17) mod 5
LHS = 31 mod 5
LHS = 1
RHS = (A mod C + B mod C) mod C
RHS = (14 mod 5 + 17 mod 5) mod 5
RHS = (4 + 2) mod 5
RHS = 1
LHS = RHS = 1

模加法运算的直观理解

观察下图。 如果我们想要计算 12+9 mod 7 ,我们可以轻松在模块化圆圈上顺时针方向前进 12+9 步(如左下方圆圈所示)。
我们可以发现一条捷径,每隔7步可以回到模运算圆上的相同位置。模圆圈周围的这些完整环路对我们的最终位置没有贡献。我们通过计算每个数字mod 7 (如上面的两个模圆圈所示)忽略圆周围的这些完整循环。这将给出我们相对于0的顺时针步数,它们对模块圆周围的最终位置有贡献。
现在,我们只需绕顺时针方向绕过每个数字最终位置的总步数(如右下方模圆圈所示)。 此方法通常适用于任何两个整数和任何模圆。

证明模运算的加法属性

我们将证明 (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
(A + B) = C * (Q1 + Q2) + R1+R2
LHS = (A + B) mod C
LHS = (C * (Q1 + Q2) + R1+ R2) mod C
当我们采用mod C时我们可以消除C的倍数
LHS = (R1 + R2) mod C
RHS = (A mod C + B mod C) mod C
RHS = (R1 + R2) mod C
LHS=RHS= (R1 + R2) mod C

模运算减法

模运算减法的一个非常相似的证明

(A - B) mod C = (A mod C - B mod C) mod C

想加入讨论吗?

尚无帖子。
你会英语吗?单击此处查看更多可汗学院英文版的讨论.