Congruence relation 同余关系

本文主要是介绍Congruence relation 同余关系，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

https://en.wikipedia.org/wiki/Congruence_relation

https://zh.wikipedia.org/wiki/%E5%90%8C%E9%A4%98%E9%97%9C%E4%BF%82

在数学特别是抽象代数中，同余关系或简称同余是相容于某个代数运算的等价关系。

模算术

元型例子是模算术：对于一个正整数n，两个整数a和b被称为同余模n，如果a − b整除于n（还有一个等价的条件是它们除以n得出同样的余数）。

例如，5和11同余模3：

11 ≡ 5 (mod 3)

因为11 − 5得出6，它整除于3。或者等价的说，这两个数除以3得到相同的余数：

11 = 3×3 + 2

5 = 1×3 + 2

如果 a 1 ≡ b 1 ( mod n ) {\displaystyle a_{1}\equiv b_{1}{\pmod {n}}} $a_{1}\equiv b_{1}{\pmod {n}}$ 并且 a 2 ≡ b 2 ( mod n ) {\displaystyle a_{2}\equiv b_{2}{\pmod {n}}} $a_{2}\equiv b_{2}{\pmod {n}}$ ，则 a 1 + a 2 ≡ b 1 + b 2 ( mod n ) {\displaystyle a_{1}+a_{2}\equiv b_{1}+b_{2}{\pmod {n}}} $a_{1}+a_{2}\equiv b_{1}+b_{2}{\pmod {n}}$ 并且 a 1 a 2 ≡ b 1 b 2 ( mod n ) {\displaystyle a_{1}a_{2}\equiv b_{1}b_{2}{\pmod {n}}} $a_{1}a_{2}\equiv b_{1}b_{2}{\pmod {n}}$ 。这把同余(mod n)变成了在所有整数的环上的一个等价。

线性代数

两个实数矩阵A和B被称为合同的，如果存在可逆实数矩阵P使得

对称矩阵有实数特征值。对称矩阵的“惯性”是由正特征值的数目、零特征值的数目和负特征值的数目组成的三元组。Sylvester惯性定律声称两个对称实数矩阵是合同的，当且仅当它们有相同的惯性。所以，全等变换可以改变矩阵的特征值但不能改变特征值的符号。

对于复数矩阵，必须区分“^T合同”（A和B是^T合同，如果有可逆矩阵P使得P^TAP = B）和“*合同”（A和B是*合同，如果有可逆矩阵P使得P*AP = B）。

泛代数

想法是推广到泛代数中：代数A上的同余关系是直积A×A的子集，它既是在A上的等价关系又是A×A的子代数。

同态的核总是同余。实际上，所有同余引起自核。对于给定在A上的同余~，等价类的集合A/~可以自然的方式给出自代数的结构商代数。映射所有A的元素到它的等价类的函数是同态，这个同态的核是~。

在一个代数上的所有同余关系的格是代数格。

群的同余、正规子群和理想

在群的特殊情况下，同余关系可以用基本术语描述为：如果G是群（带有单位元e）并且~是在G上的二元关系，则~是同余只要：

给定G的任何元素a，a ~ a（自反关系）。
给定G任何的元素a和b，如果a ~ b，则b ~ a（对称关系）。
给定G的任何元素a,b和c，如果a ~ b 并且b ~ c，则a ~ c（传递关系）。
给定G的任何元素a,a',b和b' ，如果a ~ a' 并且b ~ b' ，则a * b ~ a' * b' 。
给定G的任何元素a和a' ，如果a ~ a' ，则a⁻¹ ~ a' ⁻¹（这个条件可以从其他四个条件证明，所以严格上是冗余的）。

条件1, 2和3声称~是等价关系。

同余~完全确定自G的同余于单位元的那些元素的集合{a ∈ G : a ~ e}，而这个集合是正规子群。特别是，a ~ b当且仅当b⁻¹ * a ~ e。所以替代谈论在群上同余，人们通常以正规子群的方式谈论它们；事实上，所有同余都唯一的对应于G的某个正规子群。

环理想和一般情况的核

类似的技巧允许谈论环中的核为理想来替代同余关系，在模理论中为子模来替代同余关系。

这个技巧不适用于幺半群，所以同余关系的研究在幺半群理论扮演更中心的角色。

=============================

同余运算及其基本性质

    100除以7的余数是2，意思就是说把100个东西七个七个分成一组的话最后还剩2个。余数有一个严格的定义：假如被除数是a，除数是 b（假设它们均为正整数），那么我们总能够找到一个小于b的自然数r和一个整数m，使得a=bm+r。这个r就是a除以b的余数，m被称作商。我们经常用 mod来表示取余，a除以b余r就写成a mod b = r。
    如果两个数a和b之差能被m整除，那么我们就说a和b对模数m同余（关于 m同余）。比如，100-60除以8正好除尽，我们就说100和60对于模数8同余。它的另一层含义就是说，100和60除以8的余数相同。a和b对m同余，我们记作a≡b(mod m)。比如，刚才的例子可以写成100≡60(mod 8)。你会发现这种记号到处都在用，比如和数论相关的书中就经常把a mod 3 = 1写作a≡1(mod 3)。
    之所以把同余当作一种运算，是因为同余满足运算的诸多性质。比如，同余满足等价关系。具体地说，它满足自反性（一个数永远和自己同余）、对称性（a和b同余，b和a也就同余）和传递性（a和b同余，b和c同余可以推出a和c同余）。这三个性质都是显然的。
    同余运算里还有稍微复杂一些的性质。比如，同余运算和整数加减法一样满足“等量加等量，其和不变”。小学我们就知道，等式两边可以同时加上一个相等的数。例如，a=b可以推出a+100=b+100。这样的性质在同余运算中也有：对于同一个模数m，如果a和b同余，x和y同余，那么a+x和b+y也同余。在我看来，这个结论几乎是显然的。当然，我们也可以严格证明这个定理。这个定理对减法同样有效。

性质：如果a≡b(mod m)，x≡y(mod m)，则a+x≡b+y(mod m)。
证明：条件告诉我们，可以找到p和q使得a-mp = b-mq，也存在r和s使得x-mr = y-ms。于是a-mp + x-mr = b-mq + y-ms，即a+x-m(p+r) = b+y-m(q+s)，这就告诉我们a+x和b+y除以m的余数相同。

    容易想到，两个同余式对应相乘，同余式两边仍然相等：
    如果a≡b(mod m)，x≡y(mod m)，则ax≡by(mod m)。
    证明：条件告诉我们，a-mp = b-mq，x-mr = y-ms。于是(a-mp)(x-mr) = (b-mq)(y-ms)，等式两边分别展开后必然是ax-m(…) = by-m(…)的形式，这就说明ax≡by(mod m)。

现在你知道为什么有的题要叫你“输出答案mod xxxxx的结果”了吧，那是为了避免高精度运算，因为这里的结论告诉我们在运算过程中边算边mod和算完后再mod的结果一样。假如a是一个很大的数，令b=a mod m，那么(a * 100) mod m和(b * 100) mod m的结果是完全一样的，这相当于是在a≡b (mod m)的两边同时乘以100。这些结论其实都很显然，因为同余运算只关心余数（不关心“整的部分”），完全可以每一次运算后都只保留余数。因此，整个运算过程中参与运算的数都不超过m，避免了高精度的出现。

    在证明Fermat小定理时，我们用到了这样一个定理：
    如果ac≡bc(mod m)，且c和m互质，则a≡b(mod m) （就是说同余式两边可以同时除以一个和模数互质的数）。
    证明：条件告诉我们，ac-mp = bc-mq，移项可得ac-bc = mp-mq，也就是说(a-b)c = m(p-q)。这表明，(a-b)c里需要含有因子m，但c和m互质，因此只有可能是a-b被m整除，也即a≡b(mod m)。

可能以后还要用到更多的定理，到时候在这里更新。

Matrix67原创
转贴请注明出处

===================================

https://market.cloud.edu.tw/content/senior/math/tn_t2/math05/math_magic/1/1-2.htm