signed

QiShunwang

“诚信为本、客户至上”

欧拉定理学习笔记

2021/6/3 15:43:43   来源:

欧拉定理:


前言:

数论以外怎么还有这么多欧拉定理??stO @Euler Orz


前置需要:

欧拉函数: φ ( x ) \varphi(x) φ(x) 表示小于 x x x 的正整数中和 x x x 互质的数的个数。


欧拉定理:

a , m a,m a,m 互质时, a φ ( m ) ≡ 1 ( m o d m ) a^{\varphi(m)}\equiv1\pmod m aφ(m)1(modm)

证明:

x 1 , 2 , ⋯   , φ ( m ) x_{1,2,\cdots,\varphi(m)} x1,2,,φ(m) 为小于 m m m 且与 m m m 互质的正整数, p i = a × x i p_i=a\times x_i pi=a×xi

引理1:

∀ i ≠ j , p i ≢ p j ( m o d m ) \forall i\neq j,p_i\not\equiv p_j\pmod m i=j,pipj(modm)

因为所有 x x x 小于 m m m,所以 ∣ x i − x j ∣ < m \left|x_i-x_j\right|<m xixj<m

x i ≠ x j x_i\neq x_j xi=xj

所以 m ∤ x i − x j m\nmid x_i-x_j mxixj

a , m a,m a,m 互质,

所以 m ∤ a ( x i − x j ) m\nmid a(x_i-x_j) ma(xixj)

p i ≢ p j ( m o d m ) p_i\not\equiv p_j\pmod m pipj(modm)

意为所有 p i % m p_i\%m pi%m 互不相等。

引理2:

gcd ⁡ ( p i % m , m ) = 1 \gcd(p_i\%m,m)=1 gcd(pi%m,m)=1

由于 a , m a,m a,m 互质, x i , m x_i,m xi,m 互质,所以 p i , m p_i,m pi,m 互质。

p i = k m + r p_i=km+r pi=km+r r r r p i % m p_i\%m pi%m

d = gcd ⁡ ( r , m ) d=\gcd(r,m) d=gcd(r,m),显然 m , r m,r m,r 都是 d d d 倍数。

p i = d ( k ∗ m d + r d ) p_i=d(k*\dfrac{m}{d}+\dfrac{r}{d}) pi=d(kdm+dr)

所以 gcd ⁡ ( p i , m ) = d \gcd(p_i,m)=d gcd(pi,m)=d,又 p i , m p_i,m pi,m 互质,所以 d = gcd ⁡ ( r , m ) = 1 d=\gcd(r,m)=1 d=gcd(r,m)=1

意为 p i % m p_i\%m pi%m m m m 互质,即 p i % m p_i\%m pi%m φ ( m ) \varphi(m) φ(m) 种取值。

证明:

结合引理1和引理2,所有 p i % m p_i\%m pi%m 互不相等且 p i % m p_i\%m pi%m φ ( m ) \varphi(m) φ(m) 种取值。

所以 p 1 , 2 , ⋯   , φ ( m ) % m p_{1,2,\cdots,\varphi(m)}\%m p1,2,,φ(m)%m x 1 , 2 , ⋯   , φ ( m ) x_{1,2,\cdots,\varphi(m)} x1,2,,φ(m) 是一一对应的。

所以 ∏ i = 1 φ ( m ) p i ≡ ∏ i = 1 φ ( m ) x i ( m o d m ) \prod\limits_{i=1}^{\varphi(m)}p_i\equiv \prod\limits_{i=1}^{\varphi(m)}x_i\pmod m i=1φ(m)pii=1φ(m)xi(modm)

所以 ∏ i = 1 φ ( m ) ( x i × a ) ≡ ∏ i = 1 φ ( m ) x i ( m o d m ) \prod\limits_{i=1}^{\varphi(m)}(x_i\times a)\equiv \prod\limits_{i=1}^{\varphi(m)}x_i\pmod m i=1φ(m)(xi×a)i=1φ(m)xi(modm)

所以 a φ ( m ) ∗ ∏ i = 1 φ ( m ) x i ≡ ∏ i = 1 φ ( m ) x i ( m o d m ) a^{\varphi(m)}*\prod\limits_{i=1}^{\varphi(m)}x_i\equiv \prod\limits_{i=1}^{\varphi(m)}x_i\pmod m aφ(m)i=1φ(m)xii=1φ(m)xi(modm)

所以 a φ ( m ) ≡ 1 ( m o d m ) a^{\varphi(m)}\equiv 1\pmod m aφ(m)1(modm)

证毕。

实际运用时常写成:

a , m a,m a,m 互质时, a b ≡ a ( b m o d    φ ( m ) ) ( m o d m ) a^b\equiv a^{(b\mod \varphi(m))}\pmod m aba(bmodφ(m))(modm)


扩展欧拉定理:

显然欧拉定理有个硬伤是 a , m a,m a,m 互质,扩展欧拉定理则没有这个限制,可以处理更多情况。

b ≥ φ ( m ) b\geq\varphi(m) bφ(m) 时, a b ≡ a ( b m o d    φ ( m ) + φ ( m ) ) ( m o d m ) a^b\equiv a^{(b \mod\varphi(m)+\varphi(m))}\pmod m aba(bmodφ(m)+φ(m))(modm)

证明:

m m m 的一个质因子 p p p,令 m = p r × s m=p^r\times s m=pr×s,有 gcd ⁡ ( p , s ) = 1 \gcd(p,s)=1 gcd(p,s)=1

因为欧拉函数是积性函数,所以有

  • φ ( m ) = φ ( p r ) ∗ φ ( s ) \varphi(m)=\varphi(p^r)*\varphi(s) φ(m)=φ(pr)φ(s)

由欧拉定理可知 p φ ( s ) ≡ 1 ( m o d s ) p^{\varphi(s)}\equiv1\pmod s pφ(s)1(mods),所以有 ( p φ ( s ) ) φ ( p r ) ≡ 1 φ ( p r ) ( m o d s ) (p^{\varphi(s)})^{\varphi(p^r)}\equiv1^{\varphi(p^r)}\pmod s (pφ(s))φ(pr)1φ(pr)(mods)

  • p φ ( m ) ≡ 1 ( m o d s ) p^{\varphi(m)}\equiv1\pmod s pφ(m)1(mods)

所以可设 p φ ( m ) = k s + 1 p^{\varphi(m)}=ks+1 pφ(m)=ks+1,两边同乘 p r p^{r} pr p φ ( m ) + r = k m + p r p^{\varphi(m)+r}=km+p^r pφ(m)+r=km+pr

  • p φ ( m ) + r ≡ p r ( m o d m ) p^{\varphi(m)+r}\equiv p^r\pmod m pφ(m)+rpr(modm)

b ≥ r b\geq r br 时,

  • p b ≡ p b − r ∗ p r ≡ p b − r ∗ p φ ( m ) + r ≡ p b + φ ( m ) ( m o d m ) p^b\equiv p^{b-r}*p^r\equiv p^{b-r}*p^{\varphi(m)+r}\equiv p^{b+\varphi(m)}\pmod m pbpbrprpbrpφ(m)+rpb+φ(m)(modm)

b = b − φ ( m ) b=b-\varphi(m) b=bφ(m) 则有

  • b − φ ( m ) ≥ r b-\varphi(m)\geq r bφ(m)r 时, p b − φ ( m ) ≡ p b ( m o d m ) p^{b-\varphi(m)}\equiv p^b\pmod m pbφ(m)pb(modm)

因为 φ ( m ) = φ ( p r ) ∗ φ ( s ) \varphi(m)=\varphi(p^r)*\varphi(s) φ(m)=φ(pr)φ(s),所以 φ ( p r ) ≤ φ ( m ) \varphi(p^r)\leq\varphi(m) φ(pr)φ(m)

又有 r ≤ φ ( p r ) r\leq\varphi(p^r) rφ(pr) ,感性理解一下,当 r = 1 r=1 r=1 p p p 最小为 2 2 2,$\varphi§ $ 为 1 1 1,当 r r r 增加 1 1 1 时, φ ( p ) \varphi(p) φ(p) p p p,显然有 r ≤ φ ( p r ) r\leq\varphi(p^r) rφ(pr)

  • 所以有 r ≤ φ ( m ) r\leq \varphi(m) rφ(m)

所以有

  • b ≥ 2 ∗ φ ( m ) b\geq 2*\varphi(m) b2φ(m) 时, p b − φ ( m ) ≡ p b ( m o d m ) p^{b-\varphi(m)}\equiv p^b\pmod m pbφ(m)pb(modm)

整理后可得

  • b ≥ φ ( m ) b\geq\varphi(m) bφ(m) 时, p b ≡ p ( b m o d    φ ( m ) + φ ( m ) ) ( m o d m ) p^b\equiv p^{(b \mod\varphi(m)+\varphi(m))}\pmod m pbp(bmodφ(m)+φ(m))(modm)

a a a 质因数分解,对于是 m m m 质因子的 p p p 有上式,对于不是 m m m 质因子的 p p p 有欧拉定理 p b ≡ p ( b m o d    φ ( m ) ) ≡ p ( b m o d    φ ( m ) + φ ( m ) ) ( m o d m ) p^b\equiv p^{(b\mod \varphi(m))}\equiv p^{(b \mod\varphi(m)+\varphi(m))}\pmod m pbp(bmodφ(m))p(bmodφ(m)+φ(m))(modm) ,同样满足上式,所以可以全部乘起来合并,就得到了扩展欧拉定理:

b ≥ φ ( m ) b\geq\varphi(m) bφ(m) 时, a b ≡ a ( b m o d    φ ( m ) + φ ( m ) ) ( m o d m ) a^b\equiv a^{(b \mod\varphi(m)+\varphi(m))}\pmod m aba(bmodφ(m)+φ(m))(modm)


例题:

欧拉定理一般用于模意义下高次幂降次工具人++,所以一般会组合其他东西来考比如毒瘤数据结构

1.P5091 【模板】扩展欧拉定理

题目描述已经非常清楚,但由于次数 b b b 达到了高精的范围,所以我们要用欧拉定理降次,又不保证模数 m m m 与底数 a a a 互质,所以用扩展欧拉定理。

扩展欧拉定理具体写出来是这样的:

a b ≡ { a b   (   b ≤ φ ( m )   ) a ( b m o d    φ ( m ) + φ ( m ) )   (   b > φ ( m )   ) ( m o d m ) a^b\equiv \begin{cases}a^b\ (\ b\leq \varphi(m)\ )\\a^{(b \mod\varphi(m)+\varphi(m))}\ (\ b> \varphi(m)\ )\end{cases}\pmod m ab{ab ( bφ(m) )a(bmodφ(m)+φ(m)) ( b>φ(m) )(modm)

b > φ ( m ) b> \varphi(m) b>φ(m) 时我们可以边输入 b b b 边模 $ \varphi(m)$,最后再加上 $ \varphi(m)$。但注意到因为 a , m a,m a,m 没有互质的条件,当 b ≤ φ ( m ) b\leq \varphi(m) bφ(m) a b ≡ a b + φ ( m ) ( m o d m ) a^b\equiv a^{b+\varphi(m)}\pmod m abab+φ(m)(modm) 不一定成立。所以需要在输入时判断 b b b φ ( m ) \varphi(m) φ(m) 的大小关系,从而决定是否加上 $ \varphi(m)$。

代码:
#include<bits/stdc++.h>
using namespace std;
#define int long long
int a,b,m;
int phim;
int flag;
int getphi(int n){
	if(n==1)return 1;
	int ans=n;
	for(int i=2;i*i<=n;i++){
		if(n%i==0)ans-=ans/i;
		while(n%i==0)n/=i;
	}
	if(n>1)ans-=ans/n;
	return ans;
}
int qpow(int a,int b,int mod){
	int ans=1;
	while(b){
		if(b&1)ans=(ans*a)%mod;
		a=(a*a)%mod;
		b>>=1;
	}
	return ans;
}
int getb(){
	int ans=0;
	char c=getchar();
	while(c>'9'||c<'0')c=getchar();
	while(c>='0'&&c<='9'){
		ans=ans*10+c-'0';
		if(ans>phim){
			flag=true;
			ans%=phim;
		}
		c=getchar();
	}
	return ans;
}
signed main(){
	cin>>a>>m;
	phim=getphi(m);
	b=getb();
	if(flag)b+=phim;
	cout<<qpow(a,b,m);
	return 0;
}

2.P4139 上帝与集合的正确用法

题意也被简单地概括了,即:

2 2 2 ⋯ mod ⁡   p 2^{2^{2^\cdots}}\operatorname{mod}\ p 222mod p

显然左边是一个无穷大,无穷大也能降次吗?欧拉定理又没有规定数的范围,当然是可以的。但注意到不保证 2 , p 2,p 2,p 互质,所以考虑扩展欧拉定理。把它写出来:

a b ≡ { a b   (   b ≤ φ ( p )   ) a ( b m o d    φ ( p ) + φ ( p ) )   (   b > φ ( p )   ) ( m o d p ) a^b\equiv \begin{cases}a^b\ (\ b\leq \varphi(p)\ )\\a^{(b \mod\varphi(p)+\varphi(p))}\ (\ b> \varphi(p)\ )\end{cases}\pmod p ab{ab ( bφ(p) )a(bmodφ(p)+φ(p)) ( b>φ(p) )(modp)

发现此时的 b b b 等于左边的 a b a^b ab 也是 2 2 2 ⋯ 2^{2^{2^\cdots}} 222,显然大于 φ ( p ) \varphi(p) φ(p),所以发现

2 2 2 ⋯ ≡ 2 ( 2 2 2 ⋯ m o d    φ ( p ) + φ ( p ) ) ( m o d p ) 2^{2^{2^\cdots}}\equiv 2^{(2^{2^{2^\cdots}}\mod\varphi(p)+\varphi(p))}\pmod p 2222(222modφ(p)+φ(p))(modp)

观察这一坨: 2 2 2 ⋯ m o d    φ ( p ) + φ ( p ) 2^{2^{2^\cdots}} \mod\varphi(p)+\varphi(p) 222modφ(p)+φ(p)

右边的 φ ( p ) \varphi(p) φ(p) 显然可以预处理出来,而左边的 2 2 2 ⋯ m o d    φ ( p ) 2^{2^{2^\cdots}} \mod\varphi(p) 222modφ(p) 相比 2 2 2 ⋯ m o d    p 2^{2^{2^\cdots}} \mod p 222modp 规模在减小,所以可以不断从 p p p 递归到 φ ( p ) \varphi(p) φ(p)。递归到最后会递归到 p = 1 p=1 p=1 此时就可以返回 2 2 2 ⋯ m o d    1 = 0 2^{2^{2^\cdots}} \mod 1=0 222mod1=0。这样上面这坨就能算出来,再用快速幂算一下 2 ( 2 2 2 ⋯ m o d    φ ( p ) + φ ( p ) ) 2^{(2^{2^{2^\cdots}}\mod\varphi(p)+\varphi(p))} 2(222modφ(p)+φ(p)) 就可以回溯回去了。

递归思想建立了我们可以稍加优化,由于 φ ( m ) \varphi(m) φ(m) 不断减小,所以我们可以用欧拉筛预处理出 1 1 1 p m a x p_{max} pmax 的所有 φ \varphi φ 值。且不同的 p p p 计算时可能会有重复,所以我们还可以记忆化搜索。另外在快速幂算的时候次数最大有 2 p 2p 2p 次,会爆 int,所以还要用long long

时间复杂度分析:由于偶数取 φ \varphi φ 至少减半,奇数会变成偶数,所以复杂度是 log ⁡ \log log 的。总的大概是 O ( p m a x + T log ⁡ p ) O(p_{max}+T\log p) O(pmax+Tlogp)

代码:
#include<bits/stdc++.h>
using namespace std;
#define ll long long
int prime[700005];
int phi[10000005];
void getphi(int n){
	phi[1]=1;
	for(int i=2;i<=n;i++){
		if(phi[i]==0){prime[++prime[0]]=i;phi[i]=i-1;}
		for(int j=1;j<=prime[0]&&prime[j]*i<=n;j++){
			if(i%prime[j]==0){phi[i*prime[j]]=phi[i]*prime[j];break;}
			phi[i*prime[j]]=phi[i]*(prime[j]-1);
		}
	}
}
ll qpow(ll a,ll b,ll p){
	ll ans=1;
	while(b){
		if(b&1)ans=(ans*a)%p;
		a=(a*a)%p;
		b>>=1;
	}
	return ans;
}
int T,maxp;
int p[1005];
ll ans[10000005];
ll getans(ll p){
	if(ans[p]!=-1)return ans[p];//记忆化搜索 
	ll b=getans(phi[p])+phi[p];
	ans[p]=qpow(2,b,p);
	return ans[p];
}
signed main(){
	scanf("%d",&T);
	for(int i=1;i<=T;i++){
		scanf("%d",&p[i]);
		maxp=max(maxp,p[i]);
	}
	
	getphi(maxp);//预处理phi值 
	memset(ans,-1,sizeof(ans));
	ans[1]=0;//ans[i]代表2^2^... mod i的值 
	
	for(int i=1;i<=T;i++)
		printf("%lld\n",getans(p[i]));
	return 0;
}

3.例题推荐:

这里附上两道数据结构+欧拉定理的毒瘤题,有兴趣可以做。反正我没兴趣。

P3747 [六省联考 2017] 相逢是问候.

P3934 [Ynoi2016] 炸脖龙 I.


题外话:

扩展欧拉定理证明是怎么想出来的啊,就真反常规