天天看点
返回

数论之阶与原根一、阶（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）邮件发送服务更安全更多样的推手是？

继续阅读