對於(a,n)=1的整數，滿足a^r≡1 (mod n ) 的最小整數r,稱為a模n的階。
基本介紹
- 中文名：數論階
- 外文名：Number theory
- 所屬學科：數學
- 適用領域範圍：數學
定義,性質,套用,
定義
設n>1,a是滿足（a,n）=1的整數，則必有一個r(1≤r≤n-1)使得a^r≡1 (mod n )
滿足a^r≡1 (mod n ) 的最小整數r,稱為a模n的階。
性質
(1)設（a,n）=1 ，a模n的階為r. 若正整數N使得a^N≡1(mod n ), 則 r∣N
(2)設（a,n）=1, 則a模n的階r整除ψ（n）.特別的，若n是素數p, 則a模p的階整除p-1.（費馬定理）
存在性：
設m≥2（可推廣至m≥1），（a，m）=1，
則存在正整數d≤m-1（m=1例外），使得ad≡1（mod m）。
證：
∵m≥2，（m，a）=1，
∴m不整除a。
又∵（m，a）=1，
∴m不整除aj，j≥1。
∴存在唯一一對整數qj與 rj，滿足：
aj=qjm+rj,rj∈（0，m）。
∴m個餘數r0 ，r1 ，……，rm-1僅可能取m-1個值，
∴其中必有兩個相等，設為ri=rk，0≤i<k<m，
∴m（qk -qi）= ak –ai= ai（ak-i-1）。
又∵（m，a）=1，
∴m∣ak-i-1。
∴取d=k-i，有ad≡1（mod m）。
證完。
定義：
設m≥1，（a，m）=1（或存在x0和y0，使得ax0+my0=1），d0是滿足ad≡1（mod m）的最小正整數d，記d0為δ+m（a）（簡記為δm（a）），稱為a對模m的指數（階）。
對給定的模m，d0=δ+m（a）是由a唯一確定的，是a的函式，用於刻畫與m既約的a關於模m的性質。
性質1.：
ad≡1（mod m），d≥1，充要條件是d0=δ+m（a）∣d ，即d≡0（modδ+m（a））。
證：
充分性顯然。
證必要性：
∵d0與d是整數，
∴存在唯一一對整數q與 r，滿足：
d=qd0+r, 0≤r<d0。
∴ad-1=a qd0+r - ar +ar-1= ar（a qd0 - 1）+（ar-1）。
又∵m∣ad-1，m∣aqd0-1，
∴m∣ar-1。
又∵d0的最小性，0≤r<d0，
∴r=0。
∴d0∣d 。
證完。
性質3.：
設（a，m）=1，
那么d0=δ+m（a），充要條件是ad0≡1（mod m），a0（=1），a1（=a），……，ad0-1這δ+m（a）個數對模m兩兩不同餘。
證：
證必要性：
∵d0=δ+m（a），
∴ad0≡1（mod m）。
設存在i,j，0≤i<j<d0，
使得aj≡ai（mod m）。
∵（ai，m）=1，
∴aj-i≡1（mod m）。
但1≤j-i<d0，和d0的最小性矛盾。
∴a0，a1，……，ad0-1這d0個數對模m兩兩不同餘。
證充分性：
∵a0，a1，……，ad0-1對模m兩兩不同餘，
∴aj與a0（=1）關於模m不同餘，1≤j< d0 。
又∵ad0≡1（mod m），
∴d0=δ+m（a）。
證完。
定義：
當δ+m（a）=φ（m）時，稱a是模m的原根，簡稱m的原根。
性質4.：
設（a，m）=1，
a是模m的原根，即d0=φ（m），充要條件是a0（=1），a1（=a），……， aφ（m）-1（證= ad0-1）這φ（m）個數為模m的一組既約剩餘系。
證：
證必要性：
∵（a，m）=1，
∴a0，a1，……， aφ（m）-1（= ad0-1）均和m既約。
又∵a0，a1，……， aφ（m）-1（= ad0-1）對模m兩兩不同餘，共φ（m）個數，
∴a0，a1，……， aφ（m）-1（= ad0-1）為模m的一組既約剩餘系。
證充分性：
歐拉定理aφ（m）≡1（mod m）推出。
證完。
補充：
性質1.：
若b≡a（mod m），（a，m）=1，
則δ+m（a）=δ+m（b）。
證略。
性質2.：
δ+2l（a）∣2l-2，l≥3。
證略。
性質3.：
若（a，m）=1,ak≡ak（mod m），
則k≡h（modδ+m（a））。
證略。
性質4.：
設a-1是a對模m的逆，即a-1a≡1（mod m），
有δ+m（a-1）=δ+m（a）。
證略。
定義：
設（a，m）=1（或存在x0和y0，使得ax0+my0=1），m≥2。
若有正整數d，使得m∣ad+1（即ad≡-1（mod m）），
記δ-m（a）是滿足以上性質的最小正整數d，稱為a對模m的半階。
性質1.：
當m=2時，δ+2（a）=δ-2（a）=1。
證略。
性質2.：
當m>2時，δ+m（a）=2δ-m（a）。
證：
若δ+m（a）≤δ-m（a），
∵aδ-m（a）+1=aδ+m（a）（aδ-m（a）-δ+m（a）+1），
∴m∣（aδ-m（a）-δ+m（a）+1），即aδ-m（a）-δ+m（a）≡-1（mod m）。
由δ-m（a）的最小性，知：
δ-m（a）-δ+m（a）=0。
但m>2，不可能。
∴δ+m（a）>δ-m（a）。
∵a2δ-m（a）≡1（mod m），
∴δ+m（a）∣2δ-m（a）。
又∵δ+m（a）>δ-m（a），
∴δ+m（a）=2δ-m（a）。
證完。
性質3.：
當m>2時，
m∣ah+1（即ah≡-1（mod m）），充要條件是δ-m（a）∣h，h/δ-m（a）是奇數。
證：
設h=qδ-m（a）+r，0≤r<δ-m（a），
∴ah+1=ar（a qδ-m（a） - （-1）q）+（-1）q ar+1。
∴m∣ar+（-1）q，即ar≡-（-1）q（mod m）。
∵m>2，δ-m（a）的最小性，
∴q不可能為偶數。
∴q= h/δ-m（a）是奇數。
∵δ+m（a）>δ-m（a）>r，δ-m（a）的最小性，
∴r=0。
∴δ-m（a）∣h。
證完。
性質4.：
當m∣ah+1（即ah≡-1（mod m）），或m∣ah-1（即ah≡1（mod m））時，
均有δ-m（a）∣h。
證略。
套用
1.費馬定理
