不得不啃的密码学数学基础之剩余系是个啥？数学里面有好多的定义都有前置的数学概念，要想弄懂剩余系还得先说说“同余”。一、同余    那么“同余”有是个什么呢？在谈论“同余”之前，我们先圈定个讨论的范围。接下来讨论的都是整数集合。好了！可以正式开始介绍

省选模拟赛T3一小部分用到了同余最短路，发现这简单东西自己从来没学过，补一下。\(n\)个正整数，分别为\(A_1,A_2,\cdots,A_n\)，求\([0,V]\)中有多少个数可以被表示为\(\sum\limits_{i=1}^{n}A_ix_i,x_i\in\mathbb{N}\)。可以完全背包，但复杂度\(O(nV)\)，当\(V\)很大的时候

来自潘承洞、潘承彪《初等数论》，有删改。定义1（同余类）把全体整数分为若干个两两不相交的集合，使得\((i)\)在同一个集合中的任两个数模\(m\)一定同余；\((ii)\)在两个不同集合中的任两个数模\(m\)一定不同余。每一个这样的集合称为模\(m\)的同余类。我们以\(r\bmodm\)

温馨提示:这一篇的性质非常多(不过很多性质都比较简单)1.同余若\(m|a-b\),称\(a,b\)模\(m\)同余,\(b\)是\(a\)对模\(m\)的剩余,记作\(a\equivb\pmodm

前置知识翡蜀定理与算数基本定理的证明积性函数若有一个数论函数\(f\)满足以下性质：\(\left(1\right)f\left(1\right)=1\)\(\left(2\right)\)若\(a,b\)互质，那么\(f\le