同余

我们将除以同一个数，得到余数相同的数，称为同余关系

设 (a=nq+r,b=nq'+r(n,q,q',rin N,r<n)) 则我们同样记为 (amod n=r,bmod n=r)

这读作 (a(b)) 模 (n) 等于 (r) ，由于本人是 C++ 选手，故有时也写作 (a\%n=r) 等

所以有 ((apm b)mod n=( (amod n)pm (bmod n)+n )mod n)

以及 (abmod n=(amod n)(bmod n))

同时，由于 (amod n=bmod n) 我们记为 (aequiv bequiv r(mod n))

读作：（在模 (n) 意义下，） (a) 与 (b(r)) 同余

相对地，若不同余，则写作 (a otequiv b(mod n))

同时，我们可以得到一个很重要的性质：(aequiv b(mod n)Leftrightarrow nmid (a-b))

证明也很简单： (nmid (q-q')n=( (nq+r)-(nq'+r) )=(a-b))

同余的性质

根据同余的定义，很容易得到：（证明都比较简单，不废话了）

(aequiv a(mod n))

(aequiv b(mod n)Leftrightarrow bequiv a(mod n))

(aequiv b(mod n),bequiv c(mod n)Leftrightarrow aequiv c(mod n))

若有 (aequiv b(mod n),cequiv d(mod n),kin Z,min Z_+)

(apm cequiv bpm d(mod n))

(acequiv bd(mod n))

(kaequiv kb(mod n))

(a^mequiv b^m(mod n))

当 (gcd(a,n)=1) 时 (abequiv ac(mod n)Leftrightarrow bequiv c(mod n))

很容易得到，对于 (forall min Z,nin Z_+,mmod n) 只有 (0)~(n-1) 共 (n) 种结果

故我们将所有的整数，对 (n) 分为 (n) 类，称为 (n) 的 (n) 个剩余类

对，没错，就是按余数分：将所有余数相同的数，放到一个相同的集合里，这个集合就是它所在的剩余类

而对于 (a) 所在的剩余类，我们简记为 ([a])

因此，若 (aequiv b(mod n)Leftrightarrow [a]=[b])

比如在模 (7) 意义下， ([-1]=[6]=[20]=[-13])

由于在模同一个数的意义下，剩余类可以直接视为一种特殊的数字

因此，我们支持对剩余类进行类似数字的运算：

([a]+[b]=[a+b])

([a]cdot[b]=[ab])

由于 ([a]+[0]=[0]+[a]=[a])

因此，我们认为 ([0]) 是 ([a]) 在运算中的零元

对于 ([b]+[a]=[0]) 的剩余类 ([b]) ，我们称呼为 ([a]) 的负元

又由于 ([a]cdot[1]=[a])

故认为 ([1]) 为 ([a]) 在运算中的单位元

对于 ([b]cdot[a]=[1]) 的剩余类 ([b]) ，我们称呼为 ([a]) 的逆元

并且，认为 ([a]) 是可逆的

由上面同余的性质可证明：当且仅当 (gcd(a,n)=1) 时， ([a]) 可逆