『算法-ACM 竞赛-数学-数论』数论定理-欧拉定理

定理：
若 GCD(a,m)=1，则满足$a^{\varphi (m)} \equiv 1\ (mod \ m)$

证明:

扩展欧拉定理：
$a^b\equiv
\begin{cases}
a^{b%\phi(p)}~~~~~~~~~~~gcd(a,p)=1\
a^b~~~~~~~~~~~~~~~~~~gcd(a,p)\neq1,b<\phi(p)\
a^{b%\phi(p)+\phi(p)}~~~~gcd(a,p)\neq1,b\geq\phi(p)
\end{cases}~~~~~~~(mod~p)$

证明：
当 m = 1 时显然成立，以下讨论 m ≠ 1 的情况。

对于 gcd(a,m) = 1 的情况，因为 aϕ(m) ≡ 1，所以每 ϕ(m)个 a 就相当于乘 1。于是只需要算 c Mod ϕ(m)次。

对于 c < ϕ(m)的情况，直接爆算

下面证明第三种情况。

先证明 a 是一个质数的情况：

引理 1：
∀ p 为质数，r ∈ Z+，都有 ϕ(pr) = (p−1) × pr−1。

证明：
由于 p 是一个质数，所以 1 ∼ (pr−1) 中有且仅有 i × p, i ∈ (0,pr−1) 与 pr 不互质。

于是 ϕ(pr) = pr − pr−1 = pr−1 × (p − 1) 。

证毕。
引理 2：
∀ k ∈ Z，∃ a,b,x,y ∈ Z+ , s.t. xa × yb = k，都有 a,b ≤ ϕ(k) 。

证明：
先考虑 k 为一个质数 p 的 r 次幂的情况。根据引理 1 有：

ϕ(k) = ϕ(pr) = (p−1) × pr−1。

下面说明(p−1) × pr−1 ≥ r。

当 p=2 时：

经验证 r=1,2,3 时成立。当 r>3 时按照 r 的大小做数学归纳，可证正确性。

当 p > 2 时，不等号左侧增大，右侧不变，不等式仍然成立。

考虑 k 是多个质数幂时的情况，按照质数个数做数学归纳，正确性成立。

任意组合质数，引理得证。

证毕
引理 3：∃ r ≤ c , s.t. aϕ(m)+r ≡ ar (Mod m)。
证明：
令 m = t × ar，其中 gcd(t,a)=1，t 的存在性显然。

因为 gcd(t,a) = 1，且 ϕ 函数是一个积性函数，所以 ϕ(t) | ϕ(m)。

根据欧拉定理，aϕ(t) ≡ 1 (Mod t)，于是有

aϕ(m) ≡ 1 (Mod t)

同余式同乘 ar，于是有

aϕ(m)+r ≡ ar (Mod m)

已经证明可以构造出这样的 r。根据引理 2，r ≤ ϕ(m)。又 c ≥ ϕ(m)，于是可证构造出的 r ≤ c。定理得证。

证毕
于是

ac ≡ ac−r+r ≡ ac−r+ϕ(m)+r ≡ ac+ϕ(m) (Mod m)

对上式做数学归纳，可得 ac ≡ ac+kϕ(m) , k ∈ Z，需保证指数为正。

于是最小的合法的指数即为 c Mod ϕ(m) + ϕ(m)。

于是有
ac ≡ ac Mod ϕ(m) + ϕ(m)

当 a 是一个质数的幂次时，设 a=pk，则

ac ≡ pck ≡ pck+ϕ(m) ≡ pck+kϕ(m) ≡ (pk)c+ϕ(m) ≡ (pk)c Mod ϕ(m) + ϕ(m) (Mod m)

当 a 时多个质数次幂的乘积时，依据唯一分解定理做数学归纳，即证正确性。证毕。