你所想知道密码背后的数学——同余运算( 二 ) _同余

我们还可以观察到，在这个等价类中数与数之间相差的都是 5 的整数倍。就是说，如果我们要把所有整数模 C，那么将会得到 C 个袋子，每一个袋子中的数都差 C 的整数倍。
在数学上，我们就用 A ≡ B(mod C) 来表示在这个情况，并读作 A 同余于Bmod C 。在这个表达中，我们要注意：
1. ≡ 是一个表示相同的、等价的符号。即 A 和 B 在一个等价类中。
2. (mod C)告诉我们 A 和 B 要除的数。
3. 当以上两种情况都满足时，我们称“≡”为模 C 的同余
等价关系从上面模 5 的例子可以看出，我们把所有的整数看成一个圆饼，通过模运算将其切成了五份，分为了五个等价类，对于这种告诉我们如何分出等价类的方法，我们称为等价关系(Equivalence relation) 。
等价关系有三种性质：
- 自反性(Reflexivity)：A 与 A 有关。
- 对称性(Symmetry)：若 A 与 B 有关，那么 B 与 A 有关。
- 传递性(ransitivity)：若 A 与 B 有关，B 与 C 有关,则 A 与 C 有关。
由于同余运算也是等价关系，所以也就满足这三条性质，比如：
- 3 ≡ 3(mod 5) (自反性)
- 若 3 ≡ 8(mod 5)，那么 8 ≡ 3(mod 5) (对称性)
- 若 3 ≡ 8(mod 5)，且 8 ≡ 18(mod 5)，那么 3 ≡ 18(mod 5) (传递性)
利用这三条性质，可以帮助我们完成很多模的运算。
模的加减运算数与数之间存在加减法运算，那么模与模之间是否存在类似的呢？如果存在，这将更方便于我们的计算。
我们不妨假设模之间的运算是这样的过程：

文章插图

我们先来尝试用一个例子来验证下，假设 A=12,B=9,C=7 。
那么我们得到，等式的左边 (12+9)mod 7=0，等式的右边 (12mod 7+9mod 7)mod 7=0 。
因此，从这个例子来看，这个等式是成立的。
但是，这个等式为什么成立，它又是怎样运作的呢？我们在图形上更直观的角度来观察一下

文章插图

从上图我们可以看出，只要是围绕圆的完整环就不影响终点的位置，通过先计算 mod 7 可以帮助我们忽略围绕圆的完整步数。通过加法运算，使得他们从 0 开始，顺时针移动。
对于减法运算，我们只需要将 B 取为负数，直观上，相减就视为逆时针地移动，公式如下：

文章插图