欧拉定理：
若正整数 a , n 互质，则 aφ(n)≡1(mod n) 其中 φ(n) 是欧拉函数（1~n) 与 n 互质的数。
证明如下：
不妨设X1，X2 ...... Xφn是1~n与n互质的数。
首先我们先来考虑一些数：aX1，aX2 ...... aXφn
这些数有如下两个性质：
（1）任意两个数模n余数一定不同：（反证）若存在aX1≡aX2（mod n），则 n |（ aX1 - aX2 ），而a，n互质且（X1 - X2）< n，所以n不可能整除（ aX1 - aX2 ），也就是说
不存在aX1≡aX2（mod n）。归纳法：对于任意的与n互质的Xi均成立。故得证。
那么因为有 φn 个这样的数，Xi mod n（i=1~φn）所以就有 φn 个不同的余数，并且都是模数自然是（0~n-1）。
（2）对于任意的aXi（mod n）都与n互质。这不难想，因为a与n互质这是欧拉函数的条件，Xi是（1~n）与n互质的数的集合中的元素。所以如果a*Xi做为分子，n做为分母，那么
他们构成的显然就是一个最简分数，也就是aXi和n互质。接下来就可以用欧几里得算法：因为：gcd（aXi，n）==1所以：gcd（aXi，n）== gcd（n，aXi%n）== 1
这样，我们把上面两个性质结合一下来说，aX1（mod n），aX2（mod n） ...... aXφn（mod n）构成了一个集合（性质1证明了所有元素的互异性），并且这些数是1~n与n互
质的所有数构成的集合（性质1已说明）。这样，我们巧妙的发现了，集合{ aX1（mod n），aX2（mod n） ...... aXφn（mod n）}经过一定的排序后和集合{ X1，X2 ...... Xφn }
完全一一对应。那么：aX1（mod n）* aX2（mod n）* ...... * aXφn（mod n）= X1 * X2 * ...... * Xφn 因此：我们可以写出以下式子：
aX1 * aX2 * ...... * aXφn ≡ X1 * X2 * ...... * Xφn （mod n），即：（aφn -1）X1 * X2 * ...... * Xφn ≡ 0 （mod n）
又因为X1 * X2 * ...... * Xφn与n互质，所以， （aφn -1）| n，那么aφn ≡ 1（mod n）。欧拉定理得证。
费马小定理：
对于质数p，任意整数a，均满足：ap≡a（mod p）
证明如下：
这个可以用欧拉定理来说明：首先，我们把这个式子做一个简单变换得：ap-1 * a ≡ a（mod p） 因为a ≡ a（mod p）恒成立，所以ap-1 mod p == 1时费马小定理才成立，又因为p
是质数，所以 φn == n-1 ,所以根据欧拉定理：若a，p互质则ap-1 mod p == 1成立。那么对于a，p不互质，因为p是质数，所以，a一定是倍数ap ≡ a ≡ 0（mod p）。综上所述，费马小定理
成立，其实它算是欧拉定理的一个特例。
欧拉定理的推论：
若正整数a，n互质，那么对于任意正整数b，有ab≡ab mod φ（n）（mod n）
证明如下：（类似费马小定理的证明）
把目标式做一简单变形：ab - b mod φ（n）* ab mod φ（n）≡ ab mod φ（n）（mod n），所以接下来只需要证明ab - b mod φ（n）≡ 1 （mod n），又因为：
（ b - b mod φ（n））| φ（n），不妨设：（ b - b mod φ（n））= q*φ（n）（q为自然数），则有aq*φ（n）== （aq）φ（n），因为a，n互质，那么（aq）与n也互质，
那么就转换到了欧拉定理：（aq）φ（n）≡ 1 （mod n），成立。所以我们这个推论成立。
这个推论可以帮助我们在求幂运算的时候缩小数据范围和计算次数。具体的说：在求乘方运算时，可以先把底数对mod取模，再把指数对b mod φ（n）取模。
特别的，如果a，mod不互质，且b>φ（n）时，ab≡ab mod φ（n）+ φ（n）（mod n）。
下面我们就用这个推论来做一道题：// http://www.nyzoj.com:5283/problem/6
题目：
给定a，n求出 S=((((aa)a)a)a⋅⋅⋅⋅)a （mod 998244353）共n个a。
输入：
输入仅一行. 两个正整数a和n。
输出：
输出仅一行. 一个正整数S。
样例解释：
((22)2)2 mod 998244353 = 256
数据范围：
a，n <= 1018
思路：
先求出指数，即an-1（快速幂求解），并将指数对mod-1（因为mod是质数，那么φ（mod）= mod-1），再用更新后的指数做为新的指数用快速幂求解即可。代码如下：
#include<cstdio> typedef long long ll; ll a,n; const int M=998244353; ll mi(ll a,ll b,int mod) { ll re=1; a%=mod; while (b) { if (b&1) re=(re*a)%mod; a=(a*a)%mod; b>>=1; } return re; } int main() { scanf ("%lld%lld",&a,&n); ll t=mi(a,n-1,M-1); printf("%lld",mi(a,t,M)); return 0; }
课后例题：//poj 3696
给定一个正整数L，L <= 2*109. 问多少个8连在一起的数是L的倍数。如果不存在就输出0.
//这里省略输入输出规则，请读者自行注意
思路：
x个8连在一起可以写成8*（10x-1）*9，假设d=gcd（L，8）。那么题目可以表达为：L | 8*（10x-1）*9 ， 接下来我们做一些简单的式子变形：
L | 8*（10x-1）/9 ←→ L*9 | 8*（10x-1） ←→ 9L/d | （10x-1） ←→ 10x ≡ 1 （mod 9L/d）
引理：对于任意互质的正整数a，n，满足：ax≡1（mod n）最小的整数值 X0 是φ（n）的约数。
证明如下：
（反证法）假设X0不是φ（n）的约数，则φ（n）可以表示为：qX0 + r（0 <= r < X0)。题设有：aX0≡1（mod n），那么，aqX0≡1（mod n）且正整数a,n互质，所以有欧拉定理：
aφ(n)≡1(mod n)，即：aqX0 * ar≡1(mod n)，继而得出：ar≡1(mod n)，此时r<X0，这与X0是最小的整数值矛盾，所以假设不成立。得证。
所以，接下来我们只需要求出φ（9L/d）并将其约数带入10x ≡ 1 （mod 9L/d）验证是否成立即可。求欧拉函数和快速幂，时间复杂度为：O（√（n） * log2 n）。代码如下：
#include<cstdio> #include<algorithm> using namespace std; typedef long long ll; ll n,mod; int Case; ll gcd(ll a,ll b) { return a%b==0 ? b : gcd(b,a%b); } ll Er(ll x) { ll re=x; for (ll i=2;i*i<=x;i++) { if (x%i==0) { re=re/i*(i-1); while (x%i==0) x/=i; } } if (x>1) re=re/x*(x-1); return re; } ll mul(ll a,ll b,ll p) { ll re=0; while (b) { if (b&1) re=(re+a)%p; a=2*a%p; b>>=1; } return re; } ll ksm(ll a,ll b,ll p) { ll re=1; a%=p; while (b) { if (b&1) re=mul(re,a,p); a=mul(a,a,p); b>>=1; } return re; } int main() { while (scanf ("%lld",&n)) { if (n==0) return 0; Case++; ll d=gcd(n,8); ll phi=Er(9*n/d); mod=9*n/d; ll flag=9223372036854775806; for (ll i=1;i*i<=phi;i++) { if (phi%i==0) { if (ksm(10,i,mod)==1) flag=min(flag,i); if (ksm(10,phi/i,mod)==1) flag=min(flag,phi/i); } } flag==9223372036854775806?printf("Case %d: 0 ",Case):printf("Case %d: %lld ",Case,flag); } }