天天看點
傳回

數論之階與原根一、階（order）二、原根

文章目錄

  • 一、階（order）
    • 1.定義
    • 2.基本定理
      • 定理一
        • 内容: g c d ( a , n ) = = 1 gcd(a,n)==1 gcd(a,n)==1, a m ≡ 1 ( m o d a^m ≡1(mod am≡1(mod n ) n) n)的充要條件為 ( o r d n a ) ∣ m (ord_na)| m (ordn​a)∣m
        • 證明
      • 定理二
        • 内容： g c d ( a , n ) = = 1 gcd(a,n)==1 gcd(a,n)==1, o r d n a ∣ φ ( n ) ord_na|φ(n) ordn​a∣φ(n)
        • 證明
      • 定理三
        • 内容: g c d ( a , n ) = = 1 gcd(a,n)==1 gcd(a,n)==1, a x ≡ a y ( m o d a^x ≡a^y(mod ax≡ay(mod n ) n) n)的充要條件為 x ≡ y ( m o d x ≡y(mod x≡y(mod o r d n a ) ord_na) ordn​a)
        • 證明
      • 定理四
        • 内容:若 u u u為正整數，則 o r d n a u = o r d n a g c d ( o r d n a , u ) ord_n{a^u}=\frac{ord_na}{gcd(ord_na,u)} ordn​au=gcd(ordn​a,u)ordn​a​
        • 證明
  • 二、原根
    • 1.定義
    • 2.性質
      • 性質一（哪些數有原根）
        • 内容：模 n n n有原根的充要條件是n=2、4、 p k p^k pk、 2 p k 2p^k 2pk，其中 p p p為奇素數， k k k為正整數。
      • 性質二（若有原根，有幾個不同餘的原根）
        • 内容：當正整數 n n n有原根時，有 φ ( φ ( n ) ) φ(φ(n)) φ(φ(n))個原根。
        • 證明
        • 推廣（已知最小原根，求其他原根）
      • 性質三
        • 内容：若 a a a為模 n n n的原根，那麼 a 1 , a 2 … … a φ ( n ) a^1,a^2……a^{φ(n)} a1,a2……aφ(n)構成了模 n n n的既約剩餘系
        • 證明
    • 3.如何求原根
      • 方法
      • 例題·Primitive Roots
        • 代碼
    • 4.簡單應用

一、階（order）

1.定義

設 a a a與 n n n是互質的整數且 n > 1 n>1 n>1，使 a x ≡ 1 ( m o d a^x ≡1(mod ax≡1(mod n ) n) n) 成立

的最小正整數 x x x稱為整數 a a a模 n n n的階，記為: o r d n a ord_na ordn​a

數論之階與原根一、階（order）二、原根

2.基本定理

定理一

内容: g c d ( a , n ) = = 1 gcd(a,n)==1 gcd(a,n)==1, a m ≡ 1 ( m o d a^m ≡1(mod am≡1(mod n ) n) n)的充要條件為 ( o r d n a ) ∣ m (ord_na)| m (ordn​a)∣m

證明

必要性：

已知 a o r d n a ≡ 1 ( m o d a^{ord_na} ≡1(mod aordn​a≡1(mod n ) n) n)，則可以推出： a k ∗ o r d n a ≡ 1 ( m o d a^{k*ord_na} ≡1(mod ak∗ordn​a≡1(mod n ) n) n) k 為 任 意 整 數 k為任意整數 k為任意整數 。

充分性：

反證法，若存在 m = K ∗ o r d n a + r （ 0 < = r < o r d n a ） m=K*ord_na+r（0<=r<ord_na） m=K∗ordn​a+r（0<=r<ordn​a）可使得： a m ≡ 1 ( m o d a^m ≡1(mod am≡1(mod n ) n) n)，那麼就意味着有： a r ≡ 1 ( m o d a^r ≡1(mod ar≡1(mod n ) n) n)，此時 r < o r d n a r<ord_na r<ordn​a，根據階的定義，階不應該是 o r d n a ord_na ordn​a而應該是 r r r，故産生沖突。

定理二

内容： g c d ( a , n ) = = 1 gcd(a,n)==1 gcd(a,n)==1, o r d n a ∣ φ ( n ) ord_na|φ(n) ordn​a∣φ(n)

證明

根據歐拉定理，此時有 a φ ( n ) ≡ 1 ( m o d a^{φ(n)} ≡1(mod aφ(n)≡1(mod n ) n) n),再利用定理一，就可以證明： o r d n a ∣ φ ( n ) ord_na|φ(n) ordn​a∣φ(n)

定理三

内容: g c d ( a , n ) = = 1 gcd(a,n)==1 gcd(a,n)==1, a x ≡ a y ( m o d a^x ≡a^y(mod ax≡ay(mod n ) n) n)的充要條件為 x ≡ y ( m o d x ≡y(mod x≡y(mod o r d n a ) ord_na) ordn​a)

證明

先令 o r d n a ord_na ordn​a為 d d d，有 a d ≡ 1 ( m o d a^d≡1(mod ad≡1(mod n ) n) n)

必要性：

條件轉化為 x = k ∗ d + y x=k*d+y x=k∗d+y

a x = a k ∗ d + y ≡ a y ( m o d a^x=a^{k*d+y}≡a^y(mod ax=ak∗d+y≡ay(mod n ) n) n)

充分性：

由于 g c d ( a , n ) = = 1 gcd(a,n)==1 gcd(a,n)==1，使用消去律，得： a x − y ≡ 1 ( m o d a^{x-y}≡1(mod ax−y≡1(mod n ) n) n)

由定理一可以推出 d ∣ ( x − y ) ⇒ x − y = k d ⇒ x ≡ y ( m o d d|(x-y)\Rightarrow x-y=kd\Rightarrow x≡y(mod d∣(x−y)⇒x−y=kd⇒x≡y(mod o r d n a ) ord_na) ordn​a)

定理四

内容:若 u u u為正整數，則 o r d n a u = o r d n a g c d ( o r d n a , u ) ord_n{a^u}=\frac{ord_na}{gcd(ord_na,u)} ordn​au=gcd(ordn​a,u)ordn​a​

證明

先令 o r d n a ord_na ordn​a為 d d d， t t t為 g c d ( d , u ) gcd(d,u) gcd(d,u)

那麼就可以寫為: d = p t , u = q t , ( p 與 q 互 質 ) d=pt,u=qt,(p與q互質) d=pt,u=qt,(p與q互質)

已知 a u a^u au與 n n n互質，根據定義求 o r d n a u ord_na^u ordn​au也就是求滿足: ( a u ) x ≡ 1 ( m o d (a^u)^x ≡1(mod (au)x≡1(mod n ) n) n)的最小正整數 x x x

轉化一下得： a q t x ≡ 1 ( m o d a^{qtx}≡1(mod aqtx≡1(mod n ) n) n),由定理一可知， d ∣ q t x ⇒ p t ∣ q t x ⇒ p ∣ q x d|qtx\Rightarrow pt|qtx\Rightarrow p|qx d∣qtx⇒pt∣qtx⇒p∣qx

那麼滿足整除條件的最小的 x x x就是p

是以有: o r d n a u = o r d n a g c d ( o r d n a , u ) ord_n{a^u}=\frac{ord_na}{gcd(ord_na,u)} ordn​au=gcd(ordn​a,u)ordn​a​

二、原根

1.定義

設 a a a與 n n n是互質的整數且 n > 1 n>1 n>1，則當 o r d n a = φ ( n ) ord_na=φ(n) ordn​a=φ(n)時，稱 a a a為模 n n n的原根。

即對于 a a a來說， φ ( n ) φ(n) φ(n)是滿足 a x ≡ 1 ( m o d a^{x} ≡1(mod ax≡1(mod n ) n) n)的最小正整數。

已知 a a a為模 n n n的原根，若有 a x ≡ 1 ( m o d a^{x} ≡1(mod ax≡1(mod n ) n) n)，則 x x x為 φ ( n ) φ(n) φ(n)的倍數。

2.性質

性質一（哪些數有原根）

内容：模 n n n有原根的充要條件是n=2、4、 p k p^k pk、 2 p k 2p^k 2pk，其中 p p p為奇素數， k k k為正整數。

證明可見此處

性質二（若有原根，有幾個不同餘的原根）

内容：當正整數 n n n有原根時，有 φ ( φ ( n ) ) φ(φ(n)) φ(φ(n))個原根。

證明

根據階中的定理四：若 u u u為正整數，則 o r d n a u = o r d n a g c d ( o r d n a , u ) ord_n{a^u}=\frac{ord_na}{gcd(ord_na,u)} ordn​au=gcd(ordn​a,u)ordn​a​

若 a a a為原根，有 o r d n a = φ ( n ) ord_na=φ(n) ordn​a=φ(n)

兩式合并，得 o r d n a u = φ ( n ) g c d ( φ ( n ) , u ) ord_n{a^u}=\frac{φ(n)}{gcd(φ(n),u)} ordn​au=gcd(φ(n),u)φ(n)​

那麼當 g c d ( φ ( n ) , u ) = 1 gcd(φ(n),u)=1 gcd(φ(n),u)=1,則有 o r d n a u = φ ( n ) ord_n{a^u}=φ(n) ordn​au=φ(n),

也就是當 g c d ( φ ( n ) , u ) = 1 gcd(φ(n),u)=1 gcd(φ(n),u)=1, a u a^u au為模 n n n的原根。

由于1與正整數都互質，是以得到結論：

當正整數 n n n有原根時，有 φ ( φ ( n ) ) φ(φ(n)) φ(φ(n))個原根。

推廣（已知最小原根，求其他原根）

當我們已經得知了最小原根為 a a a的情況下，想要求出其他不同餘的原根，就隻需要找出在 [ 1 , φ ( n ) ) [1,φ(n)) [1,φ(n))内與 φ ( n ) φ(n) φ(n)互質的數，将其作為指數，再取模求出另外的原根。

例：當 n = 9 n=9 n=9，已知最小原根為2

φ(9)=6，φ(6)=2，說明有兩個原根，與6互質的數分别為1跟5:

2 1 ( m o d 2^1(mod 21(mod 9 ) = 2 9)=2 9)=2

2 5 ( m o d 2^5(mod 25(mod 9 ) = 5 9)=5 9)=5

是以原根分别為2跟5.

性質三

内容：若 a a a為模 n n n的原根，那麼 a 1 , a 2 … … a φ ( n ) a^1,a^2……a^{φ(n)} a1,a2……aφ(n)構成了模 n n n的既約剩餘系

證明

第一步，證明 a 1 , a 2 … … a φ ( n ) a^1,a^2……a^{φ(n)} a1,a2……aφ(n)模 n n n的結果兩兩不同餘。

第二步，證明 a 1 , a 2 … … a φ ( n ) a^1,a^2……a^{φ(n)} a1,a2……aφ(n)模 n n n的結果與 n n n為互質關系。

第一步證明

反證法：若存在 i , j ( 1 ≤ i < j ≤ φ ( n ) ) i,j(1\leq i<j\leq φ(n)) i,j(1≤i<j≤φ(n))滿足 a j ≡ a i ( m o d a^j≡a^i(mod aj≡ai(mod n ) n) n)

通過消去律可以得到： a j − i ≡ 1 ( m o d a^{j-i}≡1(mod aj−i≡1(mod n ) n) n)

( j − i ) (j-i) (j−i)小于 φ ( n ) φ(n) φ(n)，但題目的原根為 a a a，說明滿足 a x ≡ 1 ( m o d a^x≡1(mod ax≡1(mod n ) n) n)的最小正整數為 φ ( n ) φ(n) φ(n),産生沖突，故不存在。

也就是 a 1 , a 2 … … a φ ( n ) a^1,a^2……a^{φ(n)} a1,a2……aφ(n)模 n n n的結果兩兩不同餘。

第二步證明

由條件可知， a a a與 n n n為互質關系，設存在 a s a^s as， s s s為正整數，問 a s a^s as模 n n n是否與 n n n互質？

設 a s ≡ b ( m o d a^s≡b(mod as≡b(mod n ) ⇒ n)\Rightarrow n)⇒ a s = k n + b a^s=kn+b as=kn+b

若 b b b與 n n n不互質，有質因子 t t t, n = u t , b = v t n=ut,b=vt n=ut,b=vt

上式可改寫為: a s = ( k u + v ) t a^s=(ku+v)t as=(ku+v)t

那麼就是說明在 a a a中同樣會包含該質因子 t t t，若包含，則與條件的 a , n a,n a,n互質相沖突，故不包含，也就是 a s a^s as(s為正整數)模 n n n仍然與 n n n保持互質關系。

3.如何求原根

方法

根據之前的分析，想要求模 n n n的所有原根，就需要

先判斷n的形式是否存在原根，

再求出最小原根，

最後逐一推出其餘的原根。

原根需要通過互質進行枚舉，但對于原根的判斷有點麻煩，是以可以直接利用公式來判斷（沒有證明）

将 φ ( n ) φ(n) φ(n)唯一分解為 p 1 k 1 p 2 k 2 … … p m k m p_1^{k_1}p_2^{k_2}……p_m^{k_m} p1k1​​p2k2​​……pmkm​​的形式，

如果對于每一個質因子來說，都不滿足： a φ ( n ) p i ≡ 1 ( m o d a^{\frac{φ(n)}{p_i}}≡1(mod api​φ(n)​≡1(mod n ) n) n)

那麼就可以說明a是模n的原根。

bool check_minroot(ll a,vector<ll> tmp,ll n){//判斷是否為原根 

	int sz=tmp.size();//tmp存的是将euler[n]唯一分解的質因子
	for(int i=0;i<sz;i++){
		if(Pow(a,euler[n]/tmp[i],n)==1)return 0;
	}
	return 1;
}

例題·Primitive Roots

Primitive Roots

代碼 

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll a[100005], len;
const int N=1e6+10;
int primes[N], euler[N], cnt;
bool st[N];

void get_eulers(){ //歐拉篩的擴充，同時求歐拉函數 
	int n=N;
	euler[1] = 1;
	st[0]=st[1]=1;
	for (int i=2; i <= n; i++ ){
		if ( !st[i] ){
			primes[cnt++] = i;
			euler[i] = i-1;
		}
		for ( int j=0; primes[j] <= n/i; j++ ){
			st[ primes[j]*i ] = true;
			if ( i % primes[j] == 0 ) {
				euler[ i*primes[j] ] = euler[i] * primes[j];
				break;
			}
			euler[ i*primes[j] ] = euler[i] * ( primes[j]-1 );
		}
	}
}

ll Pow(ll x,ll y,ll mod){//帶模快速幂 
	ll ans=1;
	while(y){
		if(y&1){
			ans=(ans*x)%mod;
		}
		y>>=1;
		x=(x*x)%mod;//更新底數 
	}
	return ans;
}

ll gcd(ll a,ll b){
	return b?gcd(b,a%b):a;
}

vector<ll> divide(ll n){//分解質因數 
    vector<ll> ans;
    ll tmp=sqrt(n+0.5);
    for (ll i=0; primes[i]<=tmp;i++){
        if (n%primes[i]==0){
        	ans.push_back(primes[i]); 
            while(n%primes[i]==0)
                n/=primes[i];
        }
    }
    if (n>1)
        ans.push_back(n);
    return ans;
}

bool check(ll n){
	
	if(n%2==0)n/=2;
    if(!st[n])return true;
    if(n%2==0)return false;
    
    for(ll i=1; i<cnt; i++){//判斷奇質數，是以要從3開始 
        if(n%primes[i]==0){
            while(n%primes[i]==0){
                n/=primes[i];
            }
            return n==1;
        }
    }
    return false;
} 

bool check_minroot(ll a,vector<ll> tmp,ll n){//判斷是否為最小原根 

	int sz=tmp.size();
	for(int i=0;i<sz;i++){
		if(Pow(a,euler[n]/tmp[i],n)==1)return 0;
	}
	return 1;
}
vector<ll> primitive_root(ll n){
	vector<ll> ans;//存原根 
	vector<ll> tmp;//存對φ(n)唯一分解的質因數 
	//判斷有無原根 
	if(n==2){
		ans.push_back(1);
		return ans; 
	}
	else if(n==4){
		ans.push_back(3);
		return ans;
	}
	if(!check(n)){
		return ans;	
	}

	tmp=divide(euler[n]);

	for(ll i=2;i<n;i++){//找最小原根 
		if(gcd(i,n)!=1)continue;
		if(check_minroot(i,tmp,n)){
			ans.push_back(i);
			break;
		}
	} 
	
	//計算其他的原根 
	ll temp=ans[0];
	for(int i=2;i<euler[n];i++){
		temp=temp*ans[0]%n;
		if(gcd(euler[n],i)==1){
			ans.push_back(temp);
		}
	}
	sort(ans.begin(),ans.end());
	return ans; 
}

int main(){
	get_eulers();
	ll n;
	while(~scanf("%lld",&n)){
		vector<ll>ans;
		
		ans=primitive_root(n);
		
		ll sz=ans.size();
		if(sz==0)cout<<"-1";		
		for(int i=0;i<sz;i++){
			cout<<ans[i];
			if(i<sz-1)cout<<" ";
		}
		cout<<endl;
	}	
}

4.簡單應用

當n為素數時，求解同餘方程 x 5 ≡ a ( m o d x^5≡a(mod x5≡a(mod n ) n) n)

解：

當a與n互質時，若有原根g，則必定可以用 g y ≡ a ( m o d g^y≡a(mod gy≡a(mod n ) n) n),再使用BSGS求出滿足條件的y使得 X 5 = g y X^5=g^y X5=gy有解，這個解就是原方程的解。

具體應用見于數論之名額的講解：

數論 原根
上一篇: 原根簡介
下一篇: 助力極光閃達（SendCloud）郵件發送服務更安全更多樣的推手是？

繼續閱讀