Euler & Fermat's Little Theorem 费马小定理 若 p \gcd(a, p) = 1 a^{p - 1} \equiv 1 \pmod{p}
另一个形式：对于任意整数 a a^p \equiv a \pmod{p}
证明 设一个质数为 p p a
构造一个序列： A=\{1,2,3\dots,p-1\}
\prod_{i=1}^{n}\space A_i\equiv\prod_{i=1}^{n} (A_i\times a) \pmod p 证明：
\because (A_i,p)=1,(A_i\times a,p)=1 又因为每一个 A_i\times a \pmod p A_i\times a \pmod p < p
得证（每一个 A_i\times a A_i
设 f=(p-1)! f\equiv a\times A_1\times a\times A_2\times a \times A_3 \dots \times A_{p-1} \pmod p
a^{p-1}\times f \equiv f \pmod p \\ a^{p-1} \equiv 1 \pmod p 证毕。
也可用归纳法证明：
显然 1^p\equiv 1\pmod p a^p\equiv a\pmod p
(a+1)^p=a^p+\binom{p}{1}a^{p-1}+\binom{p}{2}a^{p-2}+\cdots +\binom{p}{p-1}a+1 因为 \binom{p}{k}=\frac{p(p-1)\cdots (p-k+1)}{k!} 1\leq k\leq p-1 p \binom{p}{1}\equiv \binom{p}{2}\equiv \cdots \equiv \binom{p}{p-1}\equiv 0\pmod p (a+1)^p \equiv a^p +1\pmod p a^p\equiv a\pmod p (a+1)^p\equiv a+1\pmod p
欧拉定理 在了解欧拉定理（Euler's theorem）之前，请先了解 欧拉函数 。定理内容如下：
若 \gcd(a, m) = 1 a^{\varphi(m)} \equiv 1 \pmod{m}
证明 实际上这个证明过程跟上文费马小定理的证明过程是非常相似的：构造一个与 m ，再进行操作。
设 r_1, r_2, \cdots, r_{\varphi(m)} m ar_1, ar_2, \cdots, ar_{\varphi(m)} m r_1r_2 \cdots r_{\varphi(m)} \equiv ar_1 \cdot ar_2 \cdots ar_{\varphi(m)} \equiv a^{\varphi(m)}r_1r_2 \cdots r_{\varphi(m)} \pmod{m} r_1r_2 \cdots r_{\varphi(m)} a^{\varphi(m)} \equiv 1 \pmod{m}
当 m \varphi(m) = m - 1
扩展欧拉定理 a^b\equiv \begin{cases} a^{b\bmod\varphi(p)},\,&\gcd(a,\,p)=1\\ a^b,&\gcd(a,\,p)\ne1,\,b<\varphi(p)\\ a^{b\bmod\varphi(p)+\varphi(p)},&\gcd(a,\,p)\ne1,\,b\ge\varphi(p) \end{cases} \pmod p 证明 证明转载自 synapse7
在 a 0 1 b m r a^0 a^{r-1} r s
证明：由鸽巢定理易证。
我们把 r a m s r 0
用公式表述为： a^r\equiv a^{r+s}\pmod{m}
a
令 m=p^rm' \gcd(p,m')=1 p^{\varphi(m')}\equiv 1\pmod{m'}
又由于 \gcd(p^r,m')=1 \varphi(m') \mid \varphi(m) p^{\varphi(m)}\equiv 1 \pmod {m'} p^{\varphi(m)}=km'+1 p^r p^{r+\varphi(m)}=km+p^r m=p^rm'
所以 p^r\equiv p^{r+s}\pmod m s=\varphi(m)
推论： p^b\equiv p^{r+(b-r) \mod \varphi(m)}\pmod m
又由于 m=p^rm' \varphi(m) \ge \varphi(p^r)=p^{r-1}(p-1) \ge r
所以 p^r\equiv p^{r+\varphi(m)}\equiv p^{r \mod \varphi(m)+\varphi(m)}\pmod m
所以 p^b\equiv p^{r+(b-r) \mod \varphi(m)}\equiv p^{r \mod \varphi(m)+\varphi(m)+(b-r) \mod \varphi(m)}\equiv p^{\varphi(m)+b \mod \varphi(m)}\pmod m
即 p^b\equiv p^{b \mod \varphi(m)+\varphi(m)}\pmod m
a
是否依然有 a^{r'}\equiv a^{r'+s'}\pmod m s'=\varphi(m),a=p^k
答案是肯定的，由 2 知 p^s\equiv 1 \pmod m' p^{s \times \frac{k}{\gcd(s,k)}} \equiv 1\pmod {m'} s'=\frac{s}{\gcd(s,k)} p^{s'k}\equiv 1\pmod {m'} s' \mid s \mid \varphi(m) r'= \lceil \frac{r}{k}\rceil \le r \le \varphi(m) r',s' \varphi(m) a^b\equiv a^{b \mod \varphi(m)+\varphi(m)}\pmod m
a
只证 a
设 a=a_1a_2,a_i=p_i^{k_i} a_i s_i
则 s \mid lcm(s_1,s_2) s_1 \mid \varphi(m),s_2 \mid \varphi(m) lcm(s_1,s_2) \mid \varphi(m) s \mid \varphi(m) r=\max(\lceil \frac{r_i}{k_i} \rceil) \le \max(r_i) \le \varphi(m)
由 r,s \varphi(m) a^b\equiv a^{b \mod \varphi(m)+\varphi(m)}\pmod m
证毕。
习题 SPOJ #4141 "Euler Totient Function"[Difficulty: CakeWalk] UVA #10179 "Irreducible Basic Fractions"[Difficulty: Easy] UVA #10299 "Relatives"[Difficulty: Easy] UVA #11327 "Enumerating Rational Numbers"[Difficulty: Medium] TIMUS #1673 "Admission to Exam"[Difficulty: High] build Last update and/or translate time of this articleCheck the history edit Found smelly bugs? Translation outdated? Wanna contribute with us? Edit this Page on Github people Contributor of this article OI-wiki translate Translator of this article Visit the original article! copyright The article is available under CC BY-SA 4.0 & SATA