剩余類：
? 0≤r≤m-1(m≥1)，Cr={x∈Z | x≡ r (mod m)}={m*q+r|q∈Z}=[r](除m余r的所有數集合)，則C0,C1,C2,...,Cm-1為模m的剩余類（共有m個）
性質1：
①? x∈Z, ? 0≤r≤m-1,x∈Cr(Cr的定義)
②x,y ∈Cj,0≤j≤m-1， 當且僅當x≡y (mod m)
完全剩余系：
定義：a0,a1,a2,...,am-1是模m的一組完全剩余系《=》aj∈Cj, 0≤j≤m-1
非負最小完全剩余：0,1,2,...,m-1
性質2：
{a1,a2,...,am-1}是模m的一組完全剩余系，當且僅當 ? 1≤i<j≤m,ai ≠ aj (mod m)
性質3：
若(k,m)=1,a1,a2,...,am是模m的一組完全剩余系，則k*a1,k*a2,...,k*am-1是模m的一組完全剩余系
證明：(證明他們之間兩兩不同余)
? 1≤i<j≤m，假設 k*ai ≡ k*aj (mod m)
則 m | k*(ai-aj)
∵(m,k)=1 ∴ m | (ai-aj)
∴ai ≡ aj (mod m)
又∵ ai ≠ aj (mod m),與假設相矛盾，故假設不成立，即k*a1,k*a2,...,k*am-1之間兩兩不同余，是模m的一組完全剩余系
性質4：
若(m,n)=1,a1,a2,...,am和b1,b2,...,bn分別為模m和模n的完全剩余系，則{n*ai+m*bj | 1≤i≤m ,1≤j≤n}是模m*n的一組完全剩余系
證明：（證明在集合內兩兩不同余）
假設：n*a+m*b≡ n*α+m*β(mod m*n)
其中 a,α ∈{a1,a2,...,am}, b,β∈(b1,b2,...,bn)
故 m*n | n*(a-α)+m*(b-β)
故m | n*(a-α)+m*(b-β)
∵(m,n)=1,故m|(a-α)
即a ≡ α (mod m)
又∵ a,α ∈{a1,...,am},，故 a ≠ α (mod m)與假設矛盾，同理可證b ≡ β (mod n)與假設矛盾
故假設不成立，即n*a+m*b ≠ n*α+m*β(mod m*n)，根據性質2，可知{n*ai+m*bj | 1≤i≤m ,1≤j≤n}是模m*n的一組完全剩余系
性質5：
若n≥3,a1,a2,...,an和b1,b2,...,bn為模m的完全剩余系，則a1*b1,a2*b2,...,an*bn不為模m的一組完全剩余系
性質6：
設p為素數，則(p-1)! +1 ≡ 0 (mod p)（威爾遜定理）
（這里先舉例把，證明太復雜了！！！以后補上）
若p=2,則1!+1=2≡0 (mod 2)
若p=3,則2!+1=3≡0 (mod 3)
若p=5,則4!+1=25≡0(mod 5)
若p=7,則6!+1=721≡0 (mod 7)
...（）
縮系
定義：剩余類中與m互素的剩余類集合
數學公式表示：(Z/mz)*={Cr | 0≤r≤m-1, (r,m)=1}中的元素叫做與模m互素的剩余類(這里的元素即是集合)
|(Z/mz)*| ==>m的剩余類中與m互素的剩余類集合的個數（是有限個）
歐拉函式：φ(m)=|(Z/mz)*| 或 φ(m)={r | 0≤r≤m-1,(m,r)=1}(一個r與一個剩余類（模m余r）一 一對應)
如何求一個數的歐拉函式？
例：
對于φ(1)，完全剩余系{0}，(0,1)=1,故存在一個，即φ(1)=1
對于φ(2)，完全剩余系{0,1}，(0,2)=2,(1,2)=1,故存在一個，即φ(2)=1
對于φ(3)，完全剩余系{0,1,2}，(0,3)=3,(1,3)=1,(2,3)=1,故存在兩個，即φ(3)=2(這里以非負最小完全剩余系來為代表)
一個關于歐拉函式的結論：若p為素數，則φ(p)=p-1
性質1：設(Z/mz)*={Cr1,Cr2,...,Crφ(m)}，其中0≤r1,r2,...,rφ(m)≤m-1,a1,a2,...,aφ(m)是模m的一組縮系，則ai∈Cri, 1≤i≤φ(m)
性質2：縮系中有φ(m)個元素
性質3：若a1,a2,..,aφ(m)個與m互素的數構成模m的一組縮系，當且僅當元素兩兩不同余
性質4：(a,m)=1,{a1,a2,...,aφ(m)}是模m的一組縮系，則{a*a1,a*a2,...,a*aφ(m)}也構成模m的一組縮系
性質5：設m≥2,(a,m)=1,則a**(φ(m)) ≡ 1 (mod m)
證明：設r1,r2,...,rφ(m)是模m的一組縮系，則a*r1,a*r2,...,a*rφ(m)也為模m的一組縮系
a*r1 ≡ <a*r1> (mod m)
a*r2 ≡ <a*r2> (mod m)
.
.
.
a*rφ(m) ≡<a*rφ(m)> (mod m)
其中{a*r1,a*r2,...,a*rφ(m)}和{<a*r1>,<a*r2>,...,<a*rφ(m)>}都為模m的一組縮系
左邊相乘，右邊相乘得：
(a*r1) *(a*r2) *...*(a*rφ(m)) ≡ r1*r2*...*rφ(m) (mod m)
a**(φ(m)) *(r1*r2*...*rφ(m)) ≡ r1*r2*...*rφ(m) (mod m)
即a**(φ(m)) ≡ 1 (mod m)
性質6：設p為素數，則a**p=a (mod p)
證明：
若(a,p)=1
根據性質5可知，a**(φ(p)) ≡ 1 (mod p)
∵p為素數
∴φ(p)=p-1
∴a**(p-1) ≡ 1 (mod p)
即a**p ≡ a (mod p)
若(a,p)≠1,p為素數，則p|a ∴a**p ≡ a (mod p)(余數為0)
性質7：m≥1,n≥1,(m,n)=1,a1,a2,...aφ(m), b1,b2,...,bφ(n)分別是模m和模n的一組縮系，則{n*ai+m*bj | 0≤i≤φ(m), 0≤j≤φ(n)}是模m*n的一組縮系
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/126399.html
標籤：其他