拓展Euler定理

本節(jié)結(jié)論和證明過程均整理來自于 OI Wiki 費(fèi)馬小定理 & 歐拉定理

概述

在本節(jié)，我們將通過兩個(gè)引理，來證明拓展歐拉定理，其表述為：

對于任意正整數(shù) $a,m$ 以及非負(fù)整數(shù) $k$ ，我們有
$\begin{cases} a^k\equiv a^{k\mod\varphi(m)}\pmod m&\text{where }\mathrm{gcd}(a,m)=1\\ a^k\equiv a^{\big(k\mod\varphi(m)\big)+\varphi(m)}\pmod m&\text{where }\mathrm{gcd}(a,m)>1,\;k\geqslant\varphi(m)\\ a^k\equiv a^{k}\pmod m&\text{where }\mathrm{gcd}(a,m)>1,\;k<\varphi(m)\\ \end{cases}$
但是注意到，當(dāng) $k<\varphi(m)$ 時(shí)， $k\mod\varphi(m)$ 就是 $k$ 本身，因此第三種情況可以合并到第一種；此外，當(dāng) $a,m$ 互素時(shí)，由歐拉定理可知 $a^{\varphi(m)}\equiv1\pmod m$ ，此時(shí) $a$ 再添任意有限個(gè) $\varphi(m)$ 冪次都不影響結(jié)果，因此第一種又可以和第二種合并，于是我們可以利用示性函數(shù)（當(dāng)條件滿足取 $1$ ，否則取 $0$ ）統(tǒng)一寫為
$a^k\equiv a^{\big(k\mod\varphi(m)\big)+\varphi(m)\cdot\mathbb I(k\geqslant\varphi(m))}\pmod m$

引理1

對于任意整數(shù) $a,m\in\mathbb Z$ ，都存在一個(gè)最小的正整數(shù) $k_0>0$ ，使得
$\mathrm{gcd}\Big(a,\,\frac{m}{\mathrm{gcd}(a^{k_0},m)}\Big)=1$

證明：

若 $a,m$ 互素，則取 $k_0=1$ 即滿足條件。

下面考慮不互素的情況：設(shè)
$d=\mathrm{gcd}(a,m)=p_1^{s_1}p_2^{s_2}\cdots p_n^{s_n}>1,\;(n>0,\;s_1,s_2,\cdots,s_n>0)$
我們先從直覺上來感受這個(gè)引理的內(nèi)涵：假設(shè)取 $k_0$ 充分大——例如極限情況取到無窮大，則 $a^{k_0}$ 含有 $\prod_{i=1}^np_i^\infty$ 作為因子，于是它和 $m$ 的最大公約數(shù)中包含每一個(gè) $p_i$ ，且 $p_i$ 的冪次顯然就是 $p_i$ 在 $m$ 中的冪次，這意味著 $m$ 除以這個(gè)最大公約數(shù)后，不再含有任何 $p_i$ 作為因子，因而這個(gè)除法結(jié)果必然和 $a$ 互素。取滿足條件的最小的 $k_0$ 即可。

現(xiàn)在來給出 $a,m$ 不互素情況下的嚴(yán)格證明：我們考慮表
$\begin{cases} m&=p_1^{s_1+\delta_1}p_2^{s_2+\delta_2}\cdots p_n^{s_n+\delta_n}\cdot m''\\ a&=p_1^{s_1+\theta_1}p_2^{s_2+\theta_2}\cdots p_n^{s_n+\theta_n}\cdot a'' \end{cases},\quad(\delta_i\geqslant0,\,\theta_i\geqslant0,\;p_i\not| a'',\,p_i\not| m'',\;\forall i=1,2,\cdots,n)$
它滿足如下約束：

$\forall i=1,2,\cdots,n$ ，必有 $\delta_i\theta_i=0$ 。如若不然，存在某個(gè) $i$ 使得 $\delta_i\theta_i>0\Rightarrow\delta_i,\theta_i>0\Rightarrow\min\{\theta_i,\delta_i\}>0$ ，則 $p_i^{s_i+\min\{\delta_i,\theta_i\}}$ 是二者的公約數(shù)，但這和 $d$ 的定義矛盾；
$a'',m''$ 互素。如若不然， $a,m$ 還有第 $n+1$ 個(gè)素?cái)?shù)作為公約數(shù)，這和 $d$ 的定義矛盾。

首先，對于任意正整數(shù) $p,q$ ，我們有
$\mathrm{gcd}(a'',m'')=1\Longrightarrow\mathrm{gcd}\big((a'')^p,(m'')^q\big)=1$

這來源于最大公約數(shù)的一個(gè)性質(zhì)：若 $\mathrm{gcd}(c,a)=1$ ，則 $\mathrm{gcd}(c,ab)=\mathrm{gcd}(c,b)$ 。

于是，若令 $b\leftarrow a$ ，則從 $\mathrm{gcd}(c,a)=1$ 可以推知 $\mathrm{gcd}(c,a^2)=\mathrm{gcd}(c,a)=1$ ，進(jìn)而得出 $\mathrm{gcd}(c,a^q)=1$ 。

由最大公約數(shù)的交換律，以及再次利用得到的結(jié)果，我們就可以從 $\mathrm{gcd}(c,a)=1$ 得出 $\mathrm{gcd}(c^p,a^q)=1$ 。

我們考慮帶余除法
$s_i+\delta_i=k_i(s_i+\theta_i)+r_i,\quad(k_i\geqslant0,\;0\leqslant r_i<s_i+\theta_i)$
并令
$k_0=\max\{k_i+\mathbb I_{r_i>0}\}$
其中 $\mathbb I_{r_i>0}$ 是示性函數(shù)，僅當(dāng) $r_i>0$ 時(shí)取 $1$ ，否則取 $0$ ，從而不難看出 $k_0>0$ 。

顯然 $k_0$ 就是滿足如下條件的最小正整數(shù)
$\forall i=1,2,\cdots,n,\quad k_0(s_i+\theta_i)\geqslant s_i+\delta_i$
進(jìn)而就有
$\forall i=1,2,\cdots,n,\quad \min\{k_0(s_i+\theta_i),s_i+\delta_i\}=s_i+\delta_i$
于是，我們不難發(fā)現(xiàn)此時(shí)有
$\begin{aligned} \mathrm{gcd}(a^{k_0},m) &=\mathrm{gcd}\Big(\overline{p_1^{k_0(s_1+\theta_1)}p_2^{k_0(s_2+\theta_2)}\cdots p_n^{k_0(s_n+\theta_n)}\cdot (a'')^{k_0}}\;,\;\underline{p_1^{s_1+\delta_1}p_2^{s_2+\delta_2}\cdots p_n^{s_n+\delta_n}\cdot m''}\Big)\\ &=p_1^{\min\{k_0(s_1+\theta_1),s_1+\delta_1\}}p_2^{\min\{k_0(s_2+\theta_2),s_2+\delta_2\}}\cdots p_n^{\min\{k_0(s_n+\theta_n),s_n+\delta_n\}}\cdot\underbrace{\mathrm{gcd}\big((a'')^{k_0},m''\big)}_{=1}\\ &=p_1^{s_1+\delta_1}p_2^{s_2+\delta_2}\cdots p_n^{s_n+\delta_n} \end{aligned}$
且
$m''=m/\mathrm{gcd}(a^{k_0},m)$
于是
$\mathrm{gcd}(a,m'')=1$

□

事實(shí)上，如果我們用 $\nu_p(n)$ 表示整數(shù) $n$ 中素?cái)?shù)的冪次，則在上面證明中我們可以表示為
$\nu_{p_i}(m)=s_i+\delta_i,\;\nu_{p_i}(a)=s_i+\theta_i$
以及
$k_0=\max\left\{\left\lceil\frac{\nu_{p_i}(m)}{\nu_{p_i}(a)}\right\rceil,i=1,2,\cdots,n\right\}$
當(dāng) $a,m$ 不互素時(shí)，也可以表示為
$k_0=\max\left\{\left\lceil\frac{\nu_{p}(m)}{\nu_{p}(a)}\right\rceil:\nu_p(a)>0,\forall p\in\mathbb P\right\}$
其中 $\mathbb P$ 是所有素?cái)?shù)的集合。

引理1-推論1

設(shè) $k_0$ 是滿足引理1中結(jié)論的最小的正整數(shù)，則 $\forall k\geqslant k_0$ ，我們都有
$\mathrm{gcd}(a^k,m)=\mathrm{gcd}(a^{k_0},m)$
因而
$\mathrm{gcd}\Big(a,\,\frac{m}{\mathrm{gcd}(a^{k},m)}\Big)=\mathrm{gcd}\Big(a,\,\frac{m}{\mathrm{gcd}(a^{k_0},m)}\Big)=1$

證明：

當(dāng) $a,m$ 互素時(shí)，顯然成立。

當(dāng) $a,m$ 不互素時(shí)，由
$\forall i=1,2,\cdots,n,\quad \min\{k_0(s_i+\theta_i),s_i+\delta_i\}=s_i+\delta_i$
不難推出
$\forall i=1,2,\cdots,n,\quad \min\{k(s_i+\theta_i),s_i+\delta_i\}=s_i+\delta_i$
從而
$\begin{aligned} \mathrm{gcd}(a^{k},m) &=p_1^{\min\{k(s_1+\theta_1),s_1+\delta_1\}}p_2^{\min\{k(s_2+\theta_2),s_2+\delta_2\}}\cdots p_n^{\min\{k(s_n+\theta_n),s_n+\delta_n\}}\cdot\underbrace{\mathrm{gcd}\big((a'')^{k},m''\big)}_{=1}\\ &=p_1^{s_1+\delta_1}p_2^{s_2+\delta_2}\cdots p_n^{s_n+\delta_n}=\mathrm{gcd}(a^{k_0},m) \end{aligned}$

引理1-推論2

設(shè) $k_0$ 是滿足引理1中結(jié)論的最小的正整數(shù)，則 $\forall k_1,k_2\geqslant k_0$ ，我們都有
$\mathrm{gcd}(a^{k_1},m)=\mathrm{gcd}(a^{k_2},m)$
因而
$\mathrm{gcd}\Big(a,\,\frac{m}{\mathrm{gcd}(a^{k_1},m)}\Big)=\mathrm{gcd}\Big(a,\,\frac{m}{\mathrm{gcd}(a^{k_2},m)}\Big)=1$

證明：由推論1直接得到。

引理2

設(shè) $a,m$ 是正整數(shù)， $k_0$ 為引理1中所述，則我們有
$k_0\leqslant\varphi(m)$
其中 $\varphi(m)$ 為歐拉函數(shù)。

證明：

引入引理1最后提到的記號：
$\nu_p(m)=s\iff p^s|m\text{, and }p^{s+1}\not| m$
從而對于 $m$ 的任意素因數(shù) $p$ 有
$\begin{aligned} \varphi(m) &\geqslant\varphi(p^{\nu_p(m)})=(p-1)\cdot p^{\nu_p(m)-1}\quad\text{(By Euler Function)}\\ &\geqslant p^{\nu_p(m)-1}=\big(1+(p-1)\big)^{\nu_p(m)-1}=1+\binom{\nu_p(m)-1}{1}1^{\nu_p(m)-2}\cdot(p-1)+\dots\text{(other binomials)}\\ &\geqslant 1+(\nu_p(m)-1)\cdot(p-1)\\ &\geqslant 1+(\nu_p(m)-1)=\nu_p(m) \end{aligned}$
注意到 $k_0=\max\{k_i+\mathbb I_{r_i>0}\}$ ，其中 $s_i+\delta_i=k_i(s_i+\theta_i)+r_i,\quad(k_i\geqslant0,\;0\leqslant r_i<s_i+\theta_i)$ 如引理1中所定義，從而
$\begin{aligned} k_0 &=\max\left\{\left\lceil\frac{s_i+\delta_i}{s_i+\theta_i}\right\rceil\right\}=\max\left\{\left\lceil\frac{\nu_{p_i}(m)}{\nu_{p_i}(a)}\right\rceil\right\}\\ &\leqslant \max\nu_{p_i}(m)\\ &\leqslant\max\varphi(m)=\varphi(m) \end{aligned}$
即證明了引理2。

證明過程中用到了上取整函數(shù)的如下性質(zhì)：設(shè)正整數(shù) $s,u$ ，我們有
$\lceil s/u\rceil\leqslant s$
這是因?yàn)?，考慮帶余除法 $s=ku+r$ ，其中 $0\leqslant k\leqslant s,\;0\leqslant r<u$ ，則
$\lceil s/u\rceil=k+\mathbb I_{r>0}$
如果 $r=0$ ，則 $\mathbb I_{r>0}=0$ ，此時(shí) $\lceil s/u\rceil=k\leqslant s$ 成立；否則， $r>0$ ，此時(shí)必有 $u>1$ ，于是 $\lceil s/u\rceil=k+1$ ，假若我們有 $\lceil s/u\rceil> s$ ，則
$k+1>s=ku+r\Rightarrow 1-r>k(u-1)$
因?yàn)?img class="math-inline" src="https://math.jianshu.com/math?formula=1-r%5Cleqslant0" alt="1-r\leqslant0" mathimg="1">，這說明 $k(u-1)$ 嚴(yán)格小于 $0$ ，但這是不可能的，因?yàn)?img class="math-inline" src="https://math.jianshu.com/math?formula=u%3E1%2C%5C%2Ck%5Cgeqslant0" alt="u>1,\,k\geqslant0" mathimg="1">。

引理2-推論1

設(shè) $k_0$ 是滿足引理1中結(jié)論的最小的正整數(shù)， $\varphi$ 是歐拉函數(shù)，則
$\mathrm{gcd}(a^{\varphi(m)},m)=\mathrm{gcd}(a^{k_0},m)$
因而
$\mathrm{gcd}\Big(a,\,\frac{m}{\mathrm{gcd}(a^{\varphi(m)},m)}\Big)=\mathrm{gcd}\Big(a,\,\frac{m}{\mathrm{gcd}(a^{k_0},m)}\Big)=1$

證明：

由引理2和引理1-推論1立即可得。

拓展歐拉定理證明

基本（但不優(yōu)雅）的形式

設(shè) $a,m$ 是正整數(shù)，由引理1，可知存在一個(gè)最小的 $k_0$ 使得
$\mathrm{gcd}\Big(a,\,\frac{m}{\mathrm{gcd}(a^{k_0},m)}\Big)=1$
對于任意正整數(shù)
$k\geqslant k_0$
則由引理1的推論1得知有如下條件成立
$\mathrm{gcd}(a^k,m)=\mathrm{gcd}(a^{k_0},m),\quad \mathrm{gcd}\Big(a,\,\frac{m}{\mathrm{gcd}(a^{k},m)}\Big)=1$
現(xiàn)在考慮滿足如下同余式的整數(shù) $b$ ：
$b\equiv a^k\pmod m$
從中不難看出， $a^k,m$ 的公約數(shù)必然也是 $b$ 的公約數(shù)，由此并利用同余式的等價(jià)變形可以得到
$\frac{\mathrm{gcd}(a^{k},m)}\equiv \frac{a^k}{\mathrm{gcd}(a^{k},m)}\pmod{\frac m{\mathrm{gcd}(a^{k},m)}}$

事實(shí)上這個(gè)等價(jià)變形中我們省略敘述了一部分：同余式有等價(jià)變形 $zx\equiv zy\pmod n\iff x\equiv y\pmod{n/\mathrm{gcd}(z,m)}$ ，在上式中，模部分實(shí)際上應(yīng)該是
$\mod\frac m{\mathrm{gcd}\big(m,\underline{\mathrm{gcd}(a^k,m)}\big)}$
但一個(gè)整數(shù)和其任意正因數(shù)的最大公約數(shù)顯然還是該因數(shù)本身：
$\mathrm{gcd}\big(m,\underline{\mathrm{gcd}(a^k,m)}\big)=\underline{\mathrm{gcd}(a^k,m)}$
從而從形式上好像是等式兩邊包括模數(shù)都同時(shí)除以了 $\mathrm{gcd}(a^k,m)$ ，但一定要注意我們這里省略的步驟。

或等價(jià)寫為
$\frac{\mathrm{gcd}(a^{k_0},m)}\equiv \frac{a^{k_0}\cdot a^{k-k_0}}{\mathrm{gcd}(a^{k_0},m)}\pmod{\frac m{\mathrm{gcd}(a^{k_0},m)}}$
令
$m''=\frac m{\mathrm{gcd}(a^{k_0},m)}$
因?yàn)?img class="math-inline" src="https://math.jianshu.com/math?formula=%5Cmathrm%7Bgcd%7D(a%2Cm'')%3D1" alt="\mathrm{gcd}(a,m'')=1" mathimg="1">，由歐拉定理可知 $a^{\varphi(m'')}\equiv1\pmod{m''}$ ，則由帶余除法 $k-k_0=c\cdot\varphi(m'')+r$ 我們就有 $a^{k-k_0}=(a^{\varphi(m'')})^c\cdot a^r\equiv 1^c\cdot a^r\equiv a^r\pmod{m''}$ ，代入上面同余式得到
$\frac{\mathrm{gcd}(a^{k_0},m)}\equiv \frac{a^{k_0}}{\mathrm{gcd}(a^{k_0},m)}\cdot a^r\pmod{m''}$

注意！ 同余代換只能發(fā)生在兩個(gè)整數(shù)乘積時(shí)，對其中一個(gè)整數(shù)做替換。例如上面的過程中，因?yàn)?img class="math-inline" src="https://math.jianshu.com/math?formula=a%5E%7Bk_0%7D%2F%5Cmathrm%7Bgcd%7D(a%5E%7Bk_0%7D%2Cm)" alt="a^{k_0}/\mathrm{gcd}(a^{k_0},m)" mathimg="1">是整數(shù)， $a^{k-k_0}$ 也是整數(shù)，因此把 $a^{k-k_)}$ 代換為模 $m''$ 同余的 $a^r$ 是沒有問題的，但是，假若我們表示為
$\frac{a^s\cdot a^{k-s}}{\mathrm{gcd}(a^{k_0},m)}\in\mathbb Z$
且 $\mathrm{gcd}(a^{k_0},m)$ 不能整除 $a^s$ 時(shí)，此時(shí) $\frac{a^s}{\mathrm{gcd}(a^{k_0},m)}$ 不是整數(shù)，則不能對 $a^{k-s}$ 做同余代換！切記！

再次乘以 $\mathrm{gcd}(a^{k_0},m)$ 就有
$b\equiv a^{k_0+r}\pmod m$
因?yàn)?img class="math-inline" src="https://math.jianshu.com/math?formula=r" alt="r" mathimg="1">是帶余除法的余數(shù)， $0\leqslant r<\varphi({m''})$ ，不妨記為 $r=(k-k_0)\mod{\varphi(m'')}$ ，于是我們得到了一個(gè)直接結(jié)果
$a^k\equiv a^{k_0+\big((k-k_0)\mod{\varphi(m'')}\big)}\pmod m,\quad k\geqslant k_0$

另一方面，當(dāng) $k<k_0$ 時(shí)，可以直接計(jì)算得到
$a^k\equiv a^{k}\pmod m,\quad k< k_0$

■

但是一般要求得這樣的 $k_0$ 仍然是困難的。因此，我們可以將指數(shù)部分適當(dāng)放寬，這樣雖然增加了計(jì)算量，但是可以得出與 $k,a,m$ 直接相關(guān)的簡單形式。

寬松（但簡單）的形式

現(xiàn)在，我們來寬松一下，利用引理2的推論1結(jié)果
$\mathrm{gcd}(a^{\varphi(m)},m)=\mathrm{gcd}(a^{k_0},m)$
$\mathrm{gcd}\Big(a,\,\frac{m}{\mathrm{gcd}(a^{\varphi(m)},m)}\Big)=\mathrm{gcd}\Big(a,\,\frac{m}{\mathrm{gcd}(a^{k_0},m)}\Big)=1$
我們首先考慮 $k\geqslant \varphi(m)$ 的情況，此時(shí)由上一小節(jié)的中間結(jié)果得到
$\frac{\mathrm{gcd}(a^{\varphi(m)},m)}\equiv\frac{a^{\varphi(m)}\cdot a^{k-\varphi(m)}}{\mathrm{gcd}(a^{\varphi(m)},m)}\pmod{m''}$
考慮帶余除法
$k=w\cdot\varphi(m)+r,\quad(0\leqslant r<\varphi(m))$
以及利用歐拉函數(shù)如下性質(zhì)
$m''|m\Longrightarrow \varphi(m'')|\varphi(m)\Rightarrow \varphi(m)=c\cdot\varphi(m'')$
因?yàn)?img class="math-inline" src="https://math.jianshu.com/math?formula=a%2Cm''" alt="a,m''" mathimg="1">互素所以 $a^{\varphi(m'')}\equiv1\pmod{m''}$ ，從而
$a^{k-\varphi(m)}=a^{(w-1)\varphi(m)+r}=\big((a^{\varphi(m'')})^{c\cdot(w-1)}\cdot a^r\big)\equiv1^{c\cdot(w-1)}\cdot a^r=a^r\pmod{m''}$
對同余式做同余代換得到
$\frac{\mathrm{gcd}(a^{\varphi(m)},m)}\equiv\frac{a^{\varphi(m)}\cdot a^{r}}{\mathrm{gcd}(a^{\varphi(m)},m)}\pmod{m''}$
兩邊同時(shí)乘以 $\mathrm{gcd}(a^{\varphi(m)},m)$ ，就有
$b\equiv a^{\varphi(m)+r}\pmod m$
將 $r$ 寫為 $k\mod{\varphi(m)}$ ，我們就得到了
$a^k\equiv a^{\varphi(m)+(k\mod\varphi(m))}\pmod m,\quad k\geqslant\varphi(m)$

另一方面，當(dāng) $k<\varphi(m)$ 時(shí)， $k$ 除以 $\varphi(m)$ 的余數(shù)就是 $k$ 本身，也即
$\big(k\mod\varphi(m)\big)=k$
因此可以直接計(jì)算（利用快速冪）
$a^k\equiv a^k\pmod m,\quad k<\varphi(m)$
合起來可以統(tǒng)一用示性函數(shù)表示為（我們用 $\exp_a$ 來表示 $a$ 的冪）
$\exp_a k\equiv \exp_a\big(k\mod\varphi(m)+\varphi(m)\cdot\mathbb I_{k\geqslant\varphi(m)}\big)\pmod m$
注意，當(dāng) $a,m$ 互素時(shí)，總有 $a^{\varphi(m)}\equiv1\pmod m$ ，此時(shí)總有
$\begin{aligned} \exp_a\big(k\mod\varphi(m)+\varphi(m)\cdot\mathbb I_{k\geqslant\varphi(m)}\big) &=a^{k\mod\varphi(m)}\cdot \big(a^{\varphi(m)}\big)^{\mathbb I_{k\geqslant\varphi(m)}}\\ &\equiv a^{k\mod\varphi(m)}\cdot 1^{\mathbb I_{k\geqslant\varphi(m)}}=a^{k\mod\varphi(m)}\cdot 1\\ &=a^{k\mod\varphi(m)}\pmod m \end{aligned}$
因此互素實(shí)際上是上面這個(gè)等式的特殊情況。

色偷偷精品伊人,欧洲久久精品,欧美综合婷婷骚逼,国产AV主播,国产最新探花在线,九色在线视频一区,伊人大交九欧美,1769亚洲,黄色成人av

拓展歐拉定理證明

拓展歐拉定理證明

拓展Euler定理

概述