欧拉定理(EX及证明)
- 本篇很多推论基于质数唯一分解定理，请读者先行了解。
欧拉函数
定义
有两种：
定义欧拉函数 \(\varphi(x)\) 表示小于 \(x\) 且与 \(x\) 互质的数的个数，定义 \(1\) 与任何数互质。
定义剩余类 \(c_i\) 是 \(mod\;x=i\) 的数的集和，即所有 \(a\%x=i\) 的 \(a\)。一般可以用其中的一个 \(a\) 代表。
由于 \(gcd(a,x)=gcd(x,a\%x)\) ，所以剩余类中的数和 \(x\) 的 \(gcd\) 都是一样的。这代表了只要剩余类中有一个数和 \(x\) 互质，这个剩余类中的所有数都与 \(x\) 互质。
定义缩剩余类 是与 \(x\) 互质的数所在的剩余类。所有的缩剩余类组成缩系，一般可以从每个缩剩余类中选一个数来组成一个数列代表缩系。
定义欧拉函数 \(\varphi(x)\) 是 \(mod\;x\) 的缩剩余类个数。
性质
建议读者仔细品味欧拉函数的两个定义，下面的证明将从这两方面思考。
对于质数 \(p\) \(\varphi(p)=p-1\) 。显然成立。
对于质数 \(p\) ，\(\varphi(p^k)=p^k-p^{k-1}\) ，\(p^k\) 只与 \(p\) 的整数倍不互质。\(p^k\) 以内 一共有 \(\frac{p^k}{p}\) 个 \(p\) 的倍数。
任意大于 \(2\) 的数 \(n\) ，\(\varphi(n)\) 是偶数。因为 \(gcd(n,x)=gcd(x,n-x)\) （不会可以在本人博客找到证明），所以与 \(n\) 互质的数都是成对出现的。
欧拉函数的积性 ：（这个证法有点弱，有用 \(CRT\) 证明其通项再来证明这个的）
对于互质的两个数 \(m\) , \(n\) ，有 \(\varphi(mn)=\varphi(m)\varphi(n)\) 。
证明：
将问题分成两个子问题
设 \(x_i\) 是 \(n\) 的一个缩剩余类，\(y_i\) 是 \(m\) 的一个缩剩余类。
- 证明可以用 \(x_im+y_in\) 来表示 \(mn\) 的的一个缩剩余类，且不会重复。
- 证明 \(mn\) 的所有缩剩余类都可以用 \(x_im+y_in\) 表示。
这样就可以证明积性
下面来证明这些子问题：
Ⅰ.
\(first\) : 证明 \(x_im+y_in\) 是 \(mn\) 的的一个缩剩余类
\[\because gcd(m,n)=1\\\begin{align}gcd(x_i,n)=1\implies gcd(mx_i,n)=1\implies gcd(mx_i+ny_i,n)=1 \tag{更相减损} \\gcd(y_i,m)=1\implies gcd(ny_i,m)=1\implies gcd(ny_i+mx_i,m)=1\\\end{align}\\\therefore gcd(ny_i+mx_i,mn)=1\]
证毕。\(second\) ：证明\(x_im+y_in\) 不会重复表示一个缩剩余类
反证法：
\[\bf 设 \mit x_km+y_kn \bf和\mit x_im+y_in\bf 在\varphi(mn)的同一个缩剩余类里\\那么有：\mit x_km+y_kn\equiv x_im+y_in\quad(mod\;mn)\\\impliesx_km+y_kn\equiv x_im+y_in\quad(mod\;m)\\\impliesy_kn\equiv y_in\quad(mod\;m) \implies y_k=y_i\\\bf 同理，x_k=x_i\]
与假设矛盾，所以\(x_im+y_in\) 不会重复表示一个剩余类。Ⅱ.
设 \(Z\) 是 \(mn\) 的一个缩剩余类中的元素。
\[\begin{align}\exists\ x_0m+y_0n=1\tag{裴蜀定理}\end{align}\\\implies Zx_0m+Zy_0n=Z\\\impliesmq+np=Z\implies \gcd(mq+np,mn)=1\\\implies\gcd(mq+np,n)=1\implies \gcd(mq,n)=1\\\because \gcd(m,n)=1\quad\therefore \gcd(q,n)=1\]
所以 \(q\) 是 \(n\) 的缩剩余系中的元素，同理 \(p\) 是 \(m\) 的缩剩余系中的元素。即所有的 \(mn\) 的缩剩余类都可以用\(x_im+y_in\) 表示。欧拉函数的通向式:
\(\varphi(m)=m(1-\frac{1}{p_1})(1-\frac{1}{p_2})\dots(1-\frac{1}{p_k})\) 其中 \(k\) 是 \(m\) 的质因子。
证明：
根据唯一分解定理，我们知道任意数 \(m\) 可以表示为：\(p_1^{a_1}p_2^{a_2}\dots p_k^{a_k}\)。
由于 \(p\) 是质数， 所以\(\varphi(p_i^{a_i})=p_i^{a_i}-p_i^{a_i-1}=p_i^{a_i}(1-\frac{1}{p_i})\) （见条目 \(2.\)）。而质因子的幂彼此互质，所以
\[\varphi(m)=\varphi(p_1^{a_1})\varphi(p_2^{a_2})\dots \varphi(p_k^{a_k})=m(1-\frac{1}{p_1})(1-\frac{1}{p_2})\dots(1-\frac{1}{p_k})\]小于 \(n\) 且与其互质的数之和为 \(\frac{\varphi(n)}{2}\times n\) 。由于 \(gcd\) 我们知道小于 \(n\) 且和 \(n\) 互质的数是成对出现的，且两两相加为 \(n\) 。于是易得。
欧拉反演（等我会了再补）
如何求欧拉函数
通项公式
欧拉定理
定义
对于互质的两数 \(a\) ，\(m\) ：
\[a^{\varphi(m)}\equiv 1\quad(mod\;m)\]
证明
设 \(r_1,r_2,\dots,r_{\varphi(m)}\) 是 \(m\) 的缩剩余系，由于 \(a\) 和 \(m\) 互质，\(ar_1,ar_2,\dots,ar_{\varphi(m)}\) 也是 \(m\) 的缩剩余系。那么：
\[r_1r_2\dots r_{\varphi(m)}\equiv a^{\varphi(m)}r_1r_2\dots r_{\varphi(m)}\quad(mod\;m)\\\impliesa^{\varphi(m)} \equiv1\quad(mod\;m)\]
可以看出， \(m\) 是质数时 \(\varphi(m)=m-1\) ，即费马小定理。
代码
直接看拓欧吧。没有欧拉的板子。
扩展欧拉定理
定义
\[a^{b}\equiv\begin{cases}a^{b\%\varphi(m)}\qquad\qquad\text{gcd(a,m)=1}\\a^b\qquad\qquad\qquad\; \text{gcd(a,m)}\neq1 \quad \&\quad b\leq\varphi(m)\\a^{b\%\varphi(m)+\varphi(m)}\qquad\text{gcd(a,m)}\neq1\quad \&\quad b>\varphi(m)\end{cases}\quad(mod\ m)\]
证明
首先，我们可以简化一下问题。
我们要证
\[a^{b}\equiva^{b\%\varphi(m)+\varphi(m)}\quad(mod\;m)\\]
将 \(a\) 质因数分解，得：
\[a^b=p_1^{r_1}p_2^{r_2}\dots p_k^{r_k}\]
对于与 \(m\) 互质的 \(p_i\) ，显然有 \(p_i^{b}=p_i^{b\varphi(m)+\varphi(m)}\quad (mod\;p)\) （欧拉定理）。
那么只要证明了对于和 \(m\) 不互质的 \(p_i\) 也有此性质，就有：
\[a^b=(p_1^{r_1}p_2^{r_2}\dots p_k^{r_k})^b=(p_1^{b})^{r_1}(p_2^{b})^{r_2}\dots (p_k^{b})^{r_k}\\\quad\\=(p_1^{b\%\varphi(m)+\varphi(m)})^{r_1}(p_2^{b\%\varphi(m)+\varphi(m)})^{r_2}\dots (p_k^{b\%\varphi(m)+\varphi(m)})^{r_k}\\\quad\\=(p_1^{r_1}p_2^{r_2}\dots p_k^{r_k})^{b\%\varphi(m)+\varphi(m)}\qquad\qquad\qquad\qquad\qquad\qquad\\(mod\;m)\]
于是问题就简化成了求 \(m\) 的一个质因子 \(p\) 满足 \(p^b\equiv p^{b\%\varphi(m)+\varphi(m)}\)
证明如下：
将 \(m\) 分解成 \(p^ks\) ，由于 \(p\) 与 \(s\) 互质。就有：
\[p^{\varphi(s)}\equiv 1\quad(mod\;s)\]
又因为 \(a\equiv b \quad(mod\ s)\quad\&\quad c\equiv d\quad(mod\ s)\implies ac\equiv bd\quad(mod\ s)\) （想不通为什么可以从同余定义角度思考）。
我们可以得出 \(p^{x\times\varphi(s)}\equiv 1\quad(mod\;s)\) 。
又因为欧拉函数是积性函数，所以 \(\varphi(s)\mid\varphi(m)\) 。
就可以得出 \(p^{\varphi(m)}\equiv 1\equiv p^{\varphi(s)} \quad(mod\;s)\) 。
继续推：
\[p^{\varphi(s)}\equiv1\quad(mod\;s)\iff p^{\varphi(s)}=x\times s+1\\ \implies p^{\varphi(s)+k}=x\times s\times p^k+p^k \\ \implies p^{\varphi(s)+k}=xm+p^k\\ \implies p^{\varphi(s)+k}\equiv p^k\quad(mod\;m)\]
又因为 \(p^{\varphi(m)}\equiv p^{\varphi(s)} \quad(mod\;m)\) ，所以 \(p^{\varphi(m)+k}\equiv p^k\quad(mod\;m)\)。
由此可知有：
\[p^b\equiv p^{b-k}p^k\equiv p^{b-k+\varphi(m)+k}\equiv p^{b+\varphi(m)}\quad(mod\;m)\]条件是 \(b\geq k\) 。
这时又有一个推论： 对于\(m=p^qs\) ，有\(\varphi(m)\geq q\) 。
先单独考虑质因子 \(p^q\) ，即证明\(\varphi(p^q)=p^{q-1}(p-1)\geq q\) ，当 \(p=2\) 时为 \(p^{q-1}\geq q\)：
首先 \(q=2\) 时成立。然后对于 \(q> 2\) 的情况，我们假设 \(q-1\) 时 \(2^{q-1}\geq q-1\) 成立：
\[2^q=2\times 2^{q-1}\geq 2\times q-2\]
由于 \(q>2\) 所以 \(2^q\geq q\) ，当且仅当 \(q=2\) 时取等。
又因为 \(p^{q-1}(q-1)\) 是个增函数，\(p\) 增大时就显然成立。
那么就有 \(b\geq k \geq \varphi(m)\) 。即函数成立条件为 \(b\geq \varphi(m)\) 。
我们要将 \(b\) 尽量变小，即减去尽量多的 \(\varphi(m)\) 。而上面的函数可表示为：
\(p^{x}\equiv p^{x+\varphi(m)}\quad(mod\;m)\) ，那么将 \(x-\varphi(m)\) 代入 \(x\) 就有 \(p^{x-\varphi(m)}\equiv p^x\quad(mod\;p)\) 。注意这时定义域为 \(x-\varphi(m) \geq \varphi(m)\implies x\geq 2\varphi(m)\) 。
我们不可能一个一个地减去 \(\varphi(m)\) 最好的做法时取模，然而这样不能保证 \(x\geq 2\varphi(m)\) ，于是我们要再加上一个 \(\varphi(m)\) 。即有 \(p^b\equiv p^{b\%\varphi(m)+\varphi(m)}\quad(mod\;m) \qquad b\geq 2\varphi(m)\) 。当 \(b\) 在 \(\varphi(m)\) 和 \(2 \varphi(m)\) 之间时这么做也没有区别，我也不知道为什么要分在第三类中。
证毕。
好长。
\(\bf code\)
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
typedef int int_;
#define int long long
char bb[20000050];
int aa,m,bbb;
int phi,ans;
int gcd(int a,int b){
return b==0?a:gcd(b,a%b);
}
void exgcd(int a,int b,int &x,int &y){
if(b==0){
x=1,y=0;
}
else{
exgcd(b,a%b,y,x);
y-=(a/b)*x;
}
}
int getphi(int x){
int ret=1;
for(int i=2;i*i<=x && x!=1;i++){
if(x%i != 0) continue;
ret *= i-1;
x/=i;
while(x%i==0){
ret*=i;
x/=i;
}
}
if(x>1) ret*=x-1;
return ret;
}
int ksm(int x,int q,int p){
int ret=1;
while(q>0){
if(q&1) ret=(ret*x)%p;
x=(x*x)%p;
q>>=1;
}
return ret;
}
int_ main()
{
bool flag=false;
scanf("%lld %lld %s",&aa,&m,bb);
phi=getphi(m);
int len=strlen(bb);
for(int i=0;i<len;i++){
bbb=bbb*10+(int)(bb[i]-'0');
if(bbb>=phi){
bbb%=phi;
flag=true;
}
}
if(flag) ans=ksm(aa,bbb+phi,m);
else ans=ksm(aa,bbb,m);
printf("%lld",ans);
return 0;
}这两篇博客对我写出这篇文章帮助很大。
——\(\frak by\;thorn\_\)