本文讨论费马小定理、欧拉定理及其扩展．这些定理解决了任意模数下任意大指数的幂的计算问题．
费马小定理
费马小定理 （Fermat's little theorem）是数论中最基础的定理之一．它也是 Fermat 素性测试 的理论基础．
费马小定理
设 p p p a a a p ∤ a p\nmid a p ∤ a a p − 1 ≡ 1 ( m o d p ) a^{p-1}\equiv 1\pmod p a p − 1 ≡ 1 ( mod p )
定理
设 p p p a a a a p ≡ a ( m o d p ) a^{p}\equiv a\pmod p a p ≡ a ( mod p )
这两个同余关系在 p ∤ a p\nmid a p ∤ a p ∣ a p\mid a p ∣ a a p ≡ 0 ≡ a ( m o d p ) a^p\equiv 0\equiv a\pmod p a p ≡ 0 ≡ a ( mod p )
证明一
设 p p p p ∤ a p\nmid a p ∤ a i = 1 , 2 , ⋯ , p − 1 i=1,2,\cdots,p-1 i = 1 , 2 , ⋯ , p − 1 i a m o d p ia \bmod p ia mod p 1 ≤ i < j < p 1\le i < j < p 1 ≤ i < j < p
i a m o d p = j a m o d p . ⟺ ( j − i ) a ≡ 0. ( m o d p ) ia \bmod p = ja \bmod p. \iff (j-i)a\equiv 0.\pmod p ia mod p = j a mod p . ⟺ ( j − i ) a ≡ 0. ( mod p ) 但是，( j − i ) (j-i) ( j − i ) a a a p p p
换句话说，这些余数是 { 1 , 2 , ⋯ , p − 1 } \{1,2,\cdots,p-1\} { 1 , 2 , ⋯ , p − 1 }
∏ i = 1 p − 1 i = ∏ i = 1 p − 1 ( i a m o d p ) ≡ ∏ i = 1 p − 1 i a = a p − 1 ∏ i = 1 p − 1 i . ( m o d p ) \prod_{i=1}^{p-1}i = \prod_{i=1}^{p-1}(ia\bmod p) \equiv \prod_{i=1}^{p-1}ia = a^{p-1}\prod_{i=1}^{p-1}i.\pmod p i = 1 ∏ p − 1 i = i = 1 ∏ p − 1 ( ia mod p ) ≡ i = 1 ∏ p − 1 ia = a p − 1 i = 1 ∏ p − 1 i . ( mod p ) 这说明
( a p − 1 − 1 ) ∏ i = 1 p − 1 i ≡ 0. ( m o d p ) (a^{p-1}-1)\prod_{i=1}^{p-1}i \equiv 0. \pmod{p} ( a p − 1 − 1 ) i = 1 ∏ p − 1 i ≡ 0. ( mod p ) 也就是说，等式左侧是 p p p i = 1 , 2 , ⋯ , p − 1 i=1,2,\cdots, p-1 i = 1 , 2 , ⋯ , p − 1 p p p p ∣ ( a p − 1 − 1 ) p\mid (a^{p-1}-1) p ∣ ( a p − 1 − 1 )
证明二
注意到费马小定理的第二种表述对于所有 a ∈ N a\in\mathbf N a ∈ N
归纳起点为 0 p ≡ 0 ( m o d p ) 0^p\equiv 0\pmod p 0 p ≡ 0 ( mod p ) a ∈ N a\in\mathbf N a ∈ N a + 1 a+1 a + 1
( a + 1 ) p = a p + ( p 1 ) a p − 1 + ( p 2 ) a p − 2 + ⋯ + ( p p − 1 ) a + 1. (a+1)^p=a^p+\binom{p}{1}a^{p-1}+\binom{p}{2}a^{p-2}+\cdots +\binom{p}{p-1}a+1. ( a + 1 ) p = a p + ( 1 p ) a p − 1 + ( 2 p ) a p − 2 + ⋯ + ( p − 1 p ) a + 1. 除了首尾两项，组合数的表达式 ( p k ) = p ! k ! ( p − k ) ! \dbinom{p}{k} = \dfrac{p!}{k!(p-k)!} ( k p ) = k ! ( p − k )! p ! p p p k ≠ 0 , p k\neq 0,p k = 0 , p p p p
( a + 1 ) p ≡ a p + 1 ≡ a + 1. ( m o d p ) (a+1)^p \equiv a^p + 1\equiv a + 1. \pmod{p} ( a + 1 ) p ≡ a p + 1 ≡ a + 1. ( mod p ) 其中，第二步应用了归纳假设．因此，利用数学归纳法可知，费马小定理成立．
费马小定理的逆命题并不成立．即使对于所有与 n n n a a a a n − 1 ≡ 1 ( m o d n ) a^{n-1}\equiv 1\pmod n a n − 1 ≡ 1 ( mod n ) n n n Fermat 素性测试 一节．
欧拉定理
欧拉定理 （Euler's theorem）将费马小定理推广到了一般模数的情形，但仍然要求底数与指数互素．
欧拉定理
对于整数 m > 0 m>0 m > 0 a a a gcd ( a , m ) = 1 \gcd(a,m)=1 g cd( a , m ) = 1 a φ ( m ) ≡ 1 ( m o d m ) a^{\varphi(m)}\equiv 1\pmod{m} a φ ( m ) ≡ 1 ( mod m ) φ ( ⋅ ) \varphi(\cdot) φ ( ⋅ ) 欧拉函数 ．
证明
与费马小定理的证明一类似，仍然是取一个与 m m m
R = { r ∈ N : 0 < r < m , gcd ( r , m ) = 1 } . R = \{r\in\mathbf N : 0 < r < m,~\gcd(r,m)=1\}. R = { r ∈ N : 0 < r < m , g cd( r , m ) = 1 } . 这是模 m m m 既约剩余系 ．根据欧拉函数的定义可知，∣ R ∣ = φ ( m ) |R|=\varphi(m) ∣ R ∣ = φ ( m ) a a a
R = { a r m o d m : r ∈ R } . R = \{ar\bmod m: r\in R\}. R = { a r mod m : r ∈ R } . 这是因为，容易验证 gcd ( a r , m ) = 1 \gcd(ar,m)=1 g cd( a r , m ) = 1 r 1 , r 2 ∈ R r_1,r_2\in R r 1 , r 2 ∈ R a r 1 m o d m ar_1\bmod m a r 1 mod m a r 2 m o d m ar_2\bmod m a r 2 mod m
∏ r ∈ R r ≡ ∏ r ∈ R a r = a φ ( m ) ∏ r ∈ R r . ( m o d m ) \prod_{r\in R}r \equiv \prod_{r\in R}ar = a^{\varphi(m)}\prod_{r\in R}r. \pmod{m} r ∈ R ∏ r ≡ r ∈ R ∏ a r = a φ ( m ) r ∈ R ∏ r . ( mod m ) 再次重复之前的论证，消去 ∏ r ∈ R r \prod_{r\in R}r ∏ r ∈ R r a φ ( m ) ≡ 1 ( m o d m ) a^{\varphi(m)}\equiv 1\pmod m a φ ( m ) ≡ 1 ( mod m )
对于素数 p p p φ ( p ) = p − 1 \varphi(p)=p-1 φ ( p ) = p − 1 φ ( m ) \varphi(m) φ ( m ) λ ( m ) \lambda(m) λ ( m ) λ ( ⋅ ) \lambda(\cdot) λ ( ⋅ ) Carmichael 函数 ．关于相关结论的代数背景，可以参考 整数同余类的乘法群 一节．
扩展欧拉定理
扩展欧拉定理1 2 φ ( m ) 2\varphi(m) 2 φ ( m ) 快速幂 在 O ( log φ ( m ) ) O(\log\varphi(m)) O ( log φ ( m ))
扩展欧拉定理
对于任意正整数 m m m a a a k k k
a k ≡ { a k m o d φ ( m ) , gcd ( a , m ) = 1 , a k , gcd ( a , m ) ≠ 1 , k < φ ( m ) , a ( k m o d φ ( m ) ) + φ ( m ) , gcd ( a , m ) ≠ 1 , k ≥ φ ( m ) . ( m o d m ) a^k \equiv \begin{cases}
a^{k \bmod \varphi(m)}, &\gcd(a,m) = 1, \\
a^k, &\gcd(a,m)\ne 1, k < \varphi(m), \\
a^{(k \bmod \varphi(m)) + \varphi(m)}, &\gcd(a,m)\ne 1, k \ge \varphi(m).
\end{cases} \pmod m a k ≡ ⎩ ⎨ ⎧ a k mod φ ( m ) , a k , a ( k mod φ ( m )) + φ ( m ) , g cd( a , m ) = 1 , g cd( a , m ) = 1 , k < φ ( m ) , g cd( a , m ) = 1 , k ≥ φ ( m ) . ( mod m )
第二种情形是在说，如果 k < φ ( m ) k < \varphi(m) k < φ ( m ) φ ( m ) \varphi(m) φ ( m )
直观理解
在严格证明定理之前，可以首先直观理解定理的含义．
fermat1 考虑余数 a k m o d m a^k\bmod m a k mod m b b b [ 0 , m ) [0,m) [ 0 , m ) k k k a k m o d m ↦ a k + 1 m o d m a^k\bmod m \mapsto a^{k+1}\bmod m a k mod m ↦ a k + 1 mod m
扩展欧拉定理说明，这些循环可能是纯循环（第一种情形）或者混循环（第二、三种情形）．纯循环中，没有结点存在两个前驱，而混循环中就会出现这样的情形．因此，对于一般的情况，只需要能够求出循环节的长度和进入循环节之前的长度，就可以利用这个性质进行降幂．
严格证明
本节给出扩展欧拉定理的严格证明．
证明
首先说明，存在 k 0 ∈ N k_0\in\mathbf N k 0 ∈ N a a a m ′ : = m gcd ( a k 0 , m ) m':=\dfrac{m}{\gcd(a^{k_0},m)} m ′ := g cd( a k 0 , m ) m ν p ( n ) \nu_p(n) ν p ( n ) n n n p p p
k 0 = max { ⌈ ν p ( m ) ν p ( a ) ⌉ : ν p ( a ) > 0 } . k_0 = \max\left\{\left\lceil\dfrac{\nu_p(m)}{\nu_p(a)}\right\rceil : \nu_p(a)>0\right\}. k 0 = max { ⌈ ν p ( a ) ν p ( m ) ⌉ : ν p ( a ) > 0 } . 因为 m m m a a a a k 0 a^{k_0} a k 0 a a a m m m m ′ = m gcd ( a k 0 , m ) m'=\dfrac{m}{\gcd(a^{k_0},m)} m ′ = g cd( a k 0 , m ) m
进而，对 k ≥ k 0 k\ge k_0 k ≥ k 0
b ≡ a k . ( m o d m ) b\equiv a^k. \pmod m b ≡ a k . ( mod m ) 由于 gcd ( a k 0 , m ) = gcd ( a k , m ) ∣ b \gcd(a^{k_0},m)=\gcd(a^k,m)\mid b g cd( a k 0 , m ) = g cd( a k , m ) ∣ b gcd ( a k 0 , m ) \gcd(a^{k_0},m) g cd( a k 0 , m )
b gcd ( a k 0 , m ) = a k 0 gcd ( a k 0 , m ) ⋅ a k − k 0 . ( m o d m ′ ) \dfrac{b}{\gcd(a^{k_0},m)} = \dfrac{a^{k_0}}{\gcd(a^{k_0},m)}\cdot a^{k-k_0}. \pmod{m'} g cd( a k 0 , m ) b = g cd( a k 0 , m ) a k 0 ⋅ a k − k 0 . ( mod m ′ ) 此时，因为 a a a m ′ m' m ′
b gcd ( a k 0 , m ) ≡ a k 0 gcd ( a k 0 , m ) ⋅ a ( k − k 0 ) m o d φ ( m ′ ) . ( m o d m ′ ) \dfrac{b}{\gcd(a^{k_0},m)} \equiv \dfrac{a^{k_0}}{\gcd(a^{k_0},m)}\cdot a^{(k-k_0)\bmod\varphi(m')}. \pmod{m'} g cd( a k 0 , m ) b ≡ g cd( a k 0 , m ) a k 0 ⋅ a ( k − k 0 ) mod φ ( m ′ ) . ( mod m ′ ) 因此，再将因子 gcd ( a k 0 , m ) \gcd(a^{k_0},m) g cd( a k 0 , m )
b ≡ a k 0 ⋅ a ( k − k 0 ) m o d φ ( m ′ ) = a k 0 + ( k − k 0 ) m o d φ ( m ′ ) . ( m o d m ) b \equiv a^{k_0}\cdot a^{(k-k_0)\bmod\varphi(m')} = a^{k_0 + (k-k_0)\bmod\varphi(m')}. \pmod{m} b ≡ a k 0 ⋅ a ( k − k 0 ) mod φ ( m ′ ) = a k 0 + ( k − k 0 ) mod φ ( m ′ ) . ( mod m ) 这就得到了扩展欧拉定理的形式．式子说明，循环节的长度是 φ ( m ′ ) \varphi(m') φ ( m ′ ) k 0 k_0 k 0
此处得到的参数比扩展欧拉定理中的更紧，但是相对来说，这些参数的计算并不容易．可以说明，这些参数可以放宽到扩展欧拉定理中的情形．首先，利用 欧拉函数的表达式 可知，因为 m ′ ∣ m m'\mid m m ′ ∣ m φ ( m ′ ) ∣ φ ( m ) \varphi(m')\mid\varphi(m) φ ( m ′ ) ∣ φ ( m ) φ ( m ) \varphi(m) φ ( m ) k 0 k_0 k 0 φ ( m ) \varphi(m) φ ( m ) m ∈ N + m\in\mathbf N_+ m ∈ N + p ∣ m p\mid m p ∣ m
φ ( m ) ≥ φ ( p ν p ( m ) ) = ( p − 1 ) p ν p ( m ) − 1 ≥ p ν p ( m ) − 1 = ( 1 + ( p − 1 ) ) ν p ( m ) − 1 ≥ 1 + ( p − 1 ) ( ν p ( m ) − 1 ) ≥ 1 + ( ν p ( m ) − 1 ) = ν p ( m ) . \begin{aligned}
\varphi(m) &\ge \varphi(p^{\nu_p(m)}) = (p-1)p^{\nu_p(m)-1} \ge p^{\nu_p(m)-1} \\
&= (1+(p-1))^{\nu_p(m)-1} \ge 1 + (p-1)(\nu_p(m)-1) \\
&\ge 1 + (\nu_p(m)-1) = \nu_p(m).
\end{aligned} φ ( m ) ≥ φ ( p ν p ( m ) ) = ( p − 1 ) p ν p ( m ) − 1 ≥ p ν p ( m ) − 1 = ( 1 + ( p − 1 ) ) ν p ( m ) − 1 ≥ 1 + ( p − 1 ) ( ν p ( m ) − 1 ) ≥ 1 + ( ν p ( m ) − 1 ) = ν p ( m ) . 其中，第二行的不等式利用了二项式展开，并只保留常数项和一次项．因此，有
k 0 ≤ max { ν p ( m ) : p ∈ P } ≤ φ ( m ) . k_0 \le \max\{\nu_p(m):p\in\mathbf P\}\le \varphi(m). k 0 ≤ max { ν p ( m ) : p ∈ P } ≤ φ ( m ) . 这就完全证明了所述结论．
例题
本节通过一道例题展示扩展欧拉定理的一个经典应用——计算任意模数下的幂塔．幂塔 （power tower）指形如 A ↑ ( B ↑ ( C ↑ ( D ↑ ⋯ ) ) ) A\uparrow(B\uparrow(C\uparrow(D\uparrow\cdots))) A ↑ ( B ↑ ( C ↑ ( D ↑ ⋯ ))) ↑ \uparrow ↑ A , B , C , D , ⋯ A,B,C,D,\cdots A , B , C , D , ⋯
Library Checker - Tetration Mod
T T T A , B , M A,B,M A , B , M ( A ↑ ↑ B ) m o d M (A\uparrow\uparrow B)\bmod M ( A ↑↑ B ) mod M A ↑ ↑ B A\uparrow\uparrow B A ↑↑ B B B B A A A
A ↑ ↑ B = { 1 , B = 0 , A ↑ ( A ↑ ↑ ( B − 1 ) ) , B > 0. A \uparrow\uparrow B =
\begin{cases}
1 , & B = 0,\\
A\uparrow(A\uparrow\uparrow(B-1)), & B > 0.
\end{cases} A ↑↑ B = { 1 , A ↑ ( A ↑↑ ( B − 1 )) , B = 0 , B > 0. 规定 0 0 = 1 0^0=1 0 0 = 1
解答
利用 A ↑ ↑ B A\uparrow\uparrow B A ↑↑ B ( A ↑ ↑ B ) m o d M (A\uparrow\uparrow B)\bmod M ( A ↑↑ B ) mod M ( A ↑ ↑ ( B − 1 ) ) m o d φ ( M ) (A\uparrow\uparrow(B-1))\bmod\varphi(M) ( A ↑↑ ( B − 1 )) mod φ ( M ) φ ( φ ( n ) ) ≤ n / 2 \varphi(\varphi(n)) \le n/2 φ ( φ ( n )) ≤ n /2 n ≥ 2 n\ge 2 n ≥ 2 O ( log M ) O(\log M) O ( log M )
参考代码
#include <iostream>
int phi (int n) int res = n;
for (int i = 2 ; i * i <= n; ++i) {
if (n % i == 0 ) {
res = res / i * (i - 1 );
while (n % i == 0 ) n /= i;
}
}
if (n > 1 ) res = res / n * (n - 1 );
return res;
}
int mod (long long v, int m) return v >= m ? v % m + m : v; }
int pow (int a, int b, int m) long long res = 1 , po = a;
for (; b; b >>= 1 ) {
if (b & 1 ) res = mod (res * po, m);
po = mod (po * po, m);
}
return res;
}
int tetra (int a, int b, int m) if (a == 0 ) return !(b & 1 );
if (b == 0 || m == 1 ) return 1 ;
if (b == 1 ) return mod (a, m);
return pow (a, tetra (a, b - 1 , phi (m)), m);
}
int main () int t;
std::cin >> t;
for (; t; --t) {
int a, b, m;
std::cin >> a >> b >> m;
std::cout << (tetra (a, b, m) % m) << std::endl;
}
}
习题
参考资料与注释
Fermat's little theorem - Wikipedia Euler's theorem - Wikipedia Hardy, Godfrey Harold, and Edward Maitland Wright. An introduction to the theory of numbers. Oxford university press, 1979.
