南通的互联网公司网站,江西网站设计哪家好,做阿里巴巴好还是网站好,设计师作品网站简化剩余系
与完全剩余系略有区别。 我们定义数组 a i ( 1 ≤ i ≤ n ) a_i(1\le i\le n) ai(1≤i≤n) 为模 m m m 的简化剩余系#xff0c;当且仅当 ∀ 1 ≤ i , j ≤ n \forall 1\le i,j\le n ∀1≤i,j≤n#xff0c;有 a i ≢ a j ( m o d m ) a_i\not\equiv a_j…简化剩余系
与完全剩余系略有区别。 我们定义数组 a i ( 1 ≤ i ≤ n ) a_i(1\le i\le n) ai(1≤i≤n) 为模 m m m 的简化剩余系当且仅当 ∀ 1 ≤ i , j ≤ n \forall 1\le i,j\le n ∀1≤i,j≤n有 a i ≢ a j ( m o d m ) a_i\not\equiv a_j\pmod m ai≡aj(modm) ∀ 1 ≤ i ≤ n \forall 1\le i\le n ∀1≤i≤n有 gcd ( m , a i ) 1 \gcd(m,a_i)1 gcd(m,ai)1
若 a i ( 1 ≤ i ≤ n ) a_i(1\le i\le n) ai(1≤i≤n) 为模 m m m 的简化剩余系 gcd ( b , m ) 1 \gcd(b,m)1 gcd(b,m)1则 b ⋅ a i ( 1 ≤ i ≤ n ) b\cdot a_i(1\le i\le n) b⋅ai(1≤i≤n) 也为模 m m m 的简化剩余系。
简化剩余系的性质都在欧拉函数上了。。。
欧拉函数
定义欧拉函数 ϕ ( n ) \phi(n) ϕ(n) 为小于等于 n n n 且与 n n n 互质的数的个数即模 n n n 的简化剩余系的大小。
性质 ϕ ( n ) n ∏ p ∈ prime p ∣ n ( 1 − 1 p ) \phi(n)n\prod\limits_{\begin{subarray}{l}p\in\text{prime}\\p|n\end{subarray}}(1-\frac 1 p) ϕ(n)np∈primep∣n∏(1−p1)若 gcd ( n , m ) 1 \gcd(n,m)1 gcd(n,m)1则 ϕ ( n m ) ϕ ( n ) ϕ ( m ) \phi(nm)\phi(n)\phi(m) ϕ(nm)ϕ(n)ϕ(m)即 ϕ ( n ) \phi(n) ϕ(n) 为积性函数
欧拉定理
若 gcd ( a , n ) 1 \gcd(a,n)1 gcd(a,n)1则 a ϕ ( n ) ≡ 1 ( m o d n ) a^{\phi(n)}\equiv1\pmod n aϕ(n)≡1(modn) 构造 b i ( 1 ≤ i ≤ ϕ ( n ) ) b_i(1\le i\le\phi(n)) bi(1≤i≤ϕ(n)) 为模 n n n 的简化剩余系则 c i b i ⋅ a ( 1 ≤ i ≤ ϕ ( n ) ) c_ib_i\cdot a(1\le i\le\phi(n)) cibi⋅a(1≤i≤ϕ(n)) 也为模 n n n 的简化剩余系 则 ∏ i 1 ϕ ( n ) c i ≡ ∏ i 1 ϕ ( n ) b i ( m o d n ) \prod\limits^{\phi(n)}_{i1}c_i\equiv\prod\limits^{\phi(n)}_{i1}b_i\pmod n i1∏ϕ(n)ci≡i1∏ϕ(n)bi(modn) 即 ∏ i 1 ϕ ( n ) b i ⋅ a ≡ ∏ i 1 ϕ ( n ) b i ( m o d n ) \prod\limits^{\phi(n)}_{i1}b_i\cdot a\equiv\prod\limits^{\phi(n)}_{i1}b_i\pmod n i1∏ϕ(n)bi⋅a≡i1∏ϕ(n)bi(modn) 约去 ∏ i 1 ϕ ( n ) b i \prod\limits^{\phi(n)}_{i1}b_i i1∏ϕ(n)bi得 a ϕ ( n ) ≡ 1 ( m o d n ) a^{\phi(n)}\equiv1\pmod n aϕ(n)≡1(modn)证毕。
扩展欧拉定理
由欧拉定理得到扩展欧拉定理 a n ≡ a n mod ϕ ( n ) ϕ ( n ) ( m o d n ) a^n\equiv a^{n\\text{mod}\\phi(n)\phi(n)}\pmod n an≡anmodϕ(n)ϕ(n)(modn)
代码就是快速幂不贴了
习题
洛谷P5091
