本文主要是介绍【数学】完全剩余系与费马小定理，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
完全剩余系
我们定义 a i ( 1 ≤ i ≤ n ) a_i(1\le i\le n) ai(1≤i≤n) 为模 m m m 的完全剩余系当且仅当对于 1 ≤ i , j ≤ n 1\le i,j\le n 1≤i,j≤n 且 i ≠ j i\ne j i=j，满足 a i ≢ a j ( m o d m ) a_i\not\equiv a_j\pmod m ai≡aj(modm)，对于 0 ≤ i < n 0\le i<n 0≤i<n， ∃ j \exist j ∃j 使得 a j ≡ i ( m o d m ) a_j\equiv i\pmod m aj≡i(modm)。
性质1：若数组 a 1 , a 2 , ⋯ , a n a_1,a_2,\cdots,a_n a1,a2,⋯,an 为模 m m m 的完全剩余系，则 a 1 + b , a 2 + b , ⋯ , a n + b a_1+b,a_2+b,\cdots,a_n+b a1+b,a2+b,⋯,an+b 也为模 m m m 的完全剩余系。
性质2：若数组 a 1 , a 2 , ⋯ , a n a_1,a_2,\cdots,a_n a1,a2,⋯,an 为模 m m m 的完全剩余系， gcd ( b , m ) = 1 \gcd(b,m)=1 gcd(b,m)=1，则 a 1 b , a 2 b , ⋯ , a n b a_1b,a_2b,\cdots,a_nb a1b,a2b,⋯,anb 也为模 m m m 的完全剩余系。
以上两性质都可以由定义简单推导得到，不多做赘述。
费马小定理
费马小定理：设 a ∈ Z , p ∈ prime a\in\Z,p\in\text{prime} a∈Z,p∈prime，则 a p − 1 ≡ 1 ( m o d p ) a^{p-1}\equiv1\pmod p ap−1≡1(modp)。
证明：
构造 b i = a ⋅ i ( 0 ≤ i < p ) b_i=a\cdot i(0\le i<p) bi=a⋅i(0≤i<p) 显然为模 p p p 的完全剩余系
则 ∏ i = 1 p − 1 b i ≡ ∏ i = 1 p − 1 i ( m o d p ) \prod\limits^{p-1}_{i=1}b_i\equiv\prod\limits^{p-1}_{i=1}i\pmod p i=1∏p−1bi≡i=1∏p−1i(modp)
即 ∏ i = 1 p − 1 a ⋅ i ≡ ∏ i = 1 p − 1 i ( m o d p ) \prod\limits^{p-1}_{i=1}a\cdot i\equiv\prod\limits^{p-1}_{i=1}i\pmod p i=1∏p−1a⋅i≡i=1∏p−1i(modp)
约去 ∏ i = 1 p − 1 i \prod\limits^{p-1}_{i=1}i i=1∏p−1i，得 a p − 1 ≡ 1 ( m o d p ) a^{p-1}\equiv1\pmod p ap−1≡1(modp)，证毕。
费马小定理适用于求乘法逆元。
性能（求乘法逆元）
- 时间复杂度 Θ ( log p ) \Theta(\log p) Θ(logp)
代码（就是快速幂，所以不贴了）
练习
- 洛谷P3811
注：有一种线性求逆元的方法，故部分凉心题目会卡掉纯费马小定理写法。
这篇关于【数学】完全剩余系与费马小定理的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
