一个数模 m 所得的余数域。
分类完全剩余系：由{0,1,2...m−1}组成的剩余系简化剩余系：由小于 m 且与m互质的自然数组成的剩余系
完全剩余系与加法、乘法组成了一个环。
简化剩余系与四则运算构成了一个域。
结论一：若 a,b,c 为任意 3 个整数，m为正整数，且 (m,c)=1 , 则当 ac≡bc(modm) 时，有 a≡b(modm)
证明：根据题设有 (a−b)c≡0(modm) ，因为 (m,c)=1 ， c 存在关于m的逆元，两边同乘之即可证。
结论二：若 a0,a2...am−1 两两不同余，则它们构成对 m 的完全剩余系。
证明：构造同余系{0,1,...,m−1}建立起双射关系。
结论三：若 {a0,a1...am−1p} 构成对 m 的完全剩余系，(p,m)=1，则 {pa0,pa1...pam−1} 也构成对 m 的完全剩余系。
证明：利用定理一证明这m个数两两不同余再利用定理二即可。
若 p 是质数，且(a,p)=1，则 ap−1≡1(modp)
证明：构造剩余系 {1,...,p−1} ，根据定理三的思路有 {a,2a,...(p−1)a} 也构成了相同的剩余系。于是有 (p−1)!≡ap−1(p−1)!(modp) ，又有 ((p−1)!,p)=1 ，两边同乘其逆元即可。
若 a,p 为正整数且 (a,p)=1 ，则有 aφ(p)≡1(modp)
证明：与费马小定理证明思路大致相同，注意 {ax1,ax2,...,axφ(p)} 两两不同余且皆与 p 互质，其中{x1,x2,...,xφ(p)}构成了简化剩余系。
Cmn≡C⌊mp⌋⌊np⌋⋅Cm%pn%p≡∏ki=0Cmini(modp)
其中 mi,ni 分别表示 m,n 在 p 进制下的第i位的值
证明：主要沿二项式展开得到组合数来证明同余的思路。
(x+1)p=xp+C1pxp−1+...+Cp−1px+1
又有 Cba=abCb−1a−1 ，其中 a,b 为正整数。
故 (x+1)p≡xp+1(modp) ，次数变成 pk 同理。
(x+1)n=(x+1)a0[(x+1)p]a1...[(x+1)pk−1]ak−1
≡(x+1)a0(xp+1)a1...(xpk−1+1)ak−1(modp)
对比最终式子中 xm 这一项的系数就可得到
Cmn=∏ki=0Cmini(modp)
a≡b(modm)⟺m|(a−b)
同余的其中两个性质 性质一：若 a≡b(modm),n|m ，那么 a≡b(modn)证明：从定义证明即可。性质二：若 ac≡bc(modm) ，那么 a≡b(modm(m,c))
证明：显然 m(m,c)|m ，那么根据性质一， ac≡bc(modm(m,c))
由于 (c,m(m,c))=1，于是 c 关于新模数的乘法逆元存在，两边同乘之即可得。 线性同余方程
形如 ax≡b(modp) 的方程，这个方程有解当且仅当 (a,p)|b 。因为它可以化简成为 a′x≡b′(modp′) ，其中 a′=agcd(a,p) ， b′,p′ 同理，那么 x=b′a′−1 ，其中 a′−1 表示 a′ 关于 p′ 的乘法逆元。
同余方程组现有若干同余方程
x≡b0(modm0) x≡b1(modm1)… x≡bn(modmn)
要求求出通解 x
中国剩余定理这个要求mi两两互质。令 Mi=∏j≠imj ，则
x≡∑ni=0m−1iMibi(modM)
假如 mi 并非两两互质，可以先将每一个 mi 分解质因数，然后将同一个质数的判断冲突，保留模数最大的一个。最后合并就可以了。
假设我们现在需要合并两个同余方程
X≡b1(modm1)
X≡b2(modm2)
问题实际上转换成了解关于 k1,k2 的不定方程
xm1−ym2=b2−b1
用扩展 gcd 求出初解 x0,y0 。注意这一步有可能无解（ (m1,m2)∤b2−b1 ），若无解则无法合并。那么原方程的通解变成了
x=m2(m1,m2)k+b2−b1(m1,m2)x0
注意到这个方程里除了 k 是未知数以外其他都是常量。
那么我们将x带回原方程，得到
X=m1x+b1=m1m2(m1,m2)k+m1x0b2−b1(m1,m2)+b1
那么我们就成功地将两个同余方程合并成一个新的同余方程
X≡m1x0b2−b1(m1,m2)+b1(modm1m2(m1,m2))
离散对数与原根要求求解 ax≡b(modm) 的解
若 (a,m)=1 则可以应用大步小步法。
核心思想是把 ax 化成 akm+b
枚举 m ，二分b即可。
核心思想还是和求离散对数法的大步小步法一致的，只需要将矩阵和某个特定的数建立起一一对应的关系就可以了。