數論之歐拉定理

本文介紹[初等]數論、群的基本概念，并引入幾條重要定理，最後籍着這些知識簡單明了地論證了歐拉函數和歐拉定理。

數論是純粹數學的分支之一，主要研究整數的性質。

算術基本定理（用反證法易得）：又稱唯一分解定理，表述為 任何大于１的自然數，都可以唯一分解成有限個質數的乘積，公式：\(n=p_1^{a_1}p_2^{a_2}\cdots p_k^{a_k}=\prod\limits_{i=1}^kp_i^{a_i}\)，這裡\(p_i\)均為質數，其指數\(a_i\)是正整數。算術基本定理是初等數論中一條非常基本和重要的定理，它把對自然數的研究轉化為對其最基本的元素——素數的研究。

群

集合封閉性：集合中的任意個數元素經過運算所得結果仍是該集合的元素，則稱該集合在此運算法則下是封閉的。

機關元：機關元\(e\)與任意元素\(a\)運算所得結果仍為\(a\)。

逆元：若\(a*b=b*a=e\)（\(*\)表示該群的二進制運算符），則稱\(a\)與\(b\)互為逆元。

群：群是指由一個集合\(G\)和一個二進制運算符構成的代數系，對于該二進制運算符是封閉的、可結合的，擁有機關元，并且每個元素都有對應的逆元（逆元也是集合中的元素）。例如：整數集\(\mathbb{Z}\)就是一個具有加法運算(表示為\(+\))的群，其中0為機關元，任意元素\(a\)都有逆元\(-a\)。

思考：整數集在乘法運算下是否為群？

有限群是元素數目有限的群。對于有限群\(G\)的任意元素\(a\)，定義\(a^{i+1}=a * a^{i}\)，則可得到一系列元素\(a,a^2,a^3,\cdots\)（可稱為\(a\)的軌道），最後該系列元素必然會重複，因為有限群的元素是有限的。\(a\)第一次重複出現前的元素必為機關元\(e\)，\(a\)的軌道的元素個數稱為元素\(a\)的階，設為\(k\)，即有\(a^k=e\)。有限群\(G\)中任意元素的軌道都是\(G\)的一個[循環]子群。

拉格朗日 (Lagrange)定理：有限群中任意元素的階必定整除該有限群的階。（按某種方法将群中所有元素構造成一個二維數組可得）

等價類：又稱同餘類，即除以\(n\)得到相同餘數\(r\)的整數組成的子集，表示為\(\langle r\rangle_{n}\)。\(r\)可取值為0到\(n-1\)，都能得到相應的等價類，我們取每個等價類中的最小非負整數得到的集合表示為\(Z_{n}\)。顯然\(Z_{n}=\{0, \cdots, n-1\}\)，這是\(n\)的所有等價類的規範化表示，又稱為\(n\)的最小[完全]餘數系。

顯然，\(Z_{n}\)在加法運算下為一個有限群，而在乘法運算下則不是（元素未必有逆元）。我們将\(Z_{n}\)中在乘法運算下有逆元的元素的集合表示為\(Z_{n}^{*}\)，這些元素的一個特性是和\(n\)沒有公因子，如\(Z_{10}^{*}=\{1,3,7,9\} \text { 和 } Z_{12}^{*}=\{1,5,7,11\}\)。\(Z_{n}^{*}\)是乘法運算下的一個群。

歐拉定理

了解歐拉定理總是要先介紹歐拉函數。歐拉函數用于計算小于等于\(n\)且與\(n\)互素的正整數的個數，用\(\varphi(n)\)表示。顯然，小于等于\(n\)且與\(n\)互素的正整數的集合即\(Z_{n}^{*}\)。可知\(\varphi(n)=\# Z_{n}^{*}\)，其中\(\# S\)表示集合\(S\)的基數（元素個數）。若\(n\)是素數，那麼\(Z_{n}=Z_{n}^{*}\)，\(\# Z_{n}^{*}=n-1\)。

定理1.1：對于素數\(p \text { 和 } q, \varphi(pq)=\varphi(p)\varphi(q)=(p-1)(q-1), \text { 且 } \varphi(p^k)=p^{k-1}(p-1)\)。（其實前者隻要\(p, q\)互素即可滿足，可通過構造一個\(p\times q\)二維數組得到，亦或根據中國剩餘定理可推得）

證明歐拉函數通用形式：\(\varphi(x)=x\prod\limits_{i=1}^r(1-\frac{1}{p_i})\)，其中\(x>1, p_1, \cdots, p_r\text { 為 } x\)的所有質因數。

根據算術基本定理，可寫\(x=\prod\limits_{i=1}^{r}P_i^{k_i}\)，同時易證若幹素數的幂方乘積與另外若幹不同素數的幂方乘積互素，即 \((\prod\limits_{i=1}^ap_i^{j_i},\prod\limits_{i=1}^bq_i^{k_i})=1\)，于是：

依據定理1.1，\(\varphi(x)=\varphi\left(p_{1}^{k_{1}}\right) \varphi\left(p_{2}^{k_{2}}\right) \cdots \varphi\left(p_{r}^{k_{r}}\right)=p_1^{k_1-1}(p_1-1)p_2^{k_2-1}(p_2-1)\cdots p_r^{k_r-1}(p_r-1)\),

即證：\(\varphi(x)=\prod\limits_{i=1}^rp_i^{k_i-1}(p_i-1)=x\prod\limits_{i=1}^r(1-\frac{1}{p_i})\)

 注意：每種質因數隻計數一個。 比如12=2*2*3那麼根據歐拉函數φ（12）=12*（1-1/2）*(1-1/3)=4。

歐拉定理（Euler's theorem）：若\(a\)是\(Z_{n}^{*}\)的一個元素，則有\(a^{\varphi(n)}=1(\bmod n)\)。

根據歐拉函數的定義，\(\#Z_n^*=\varphi(n)\)。設\(k\)為元素\(a\)的階，根據拉格朗日定理，\(\varphi(n)\)可被\(k\)整除，即有整數\(r\)，使得\(\varphi(n)=rk\)。

又由本文前述可知，元素的階次幂等于機關元，即\(a^k=1(\bmod n)\)，于是：

\(a^{kr}=a^{\varphi(n)}=1(\bmod n)\)，得證。

歐拉定理更一般的表述：若正整數\(a,n\)互素，則\(a^{\varphi(n)}=1(\bmod n)\)。

從上述證明過程可知，如果 a 與 n 是互素的正整數，滿足同餘方程\(a^x\equiv 1\pmod{n}\)的解都是元素\(a\)的階的正整數倍。此處階可記為\(ord_na\)。

根據歐拉定理，\(a a^{\varphi(n)-1}=1(\bmod n)\)，可得\(a\)的逆元（此處又可稱模反元素）必定存在，且\(a^{-1}=a^{\varphi(n)-1}\)。

思考：費馬小定理是歐拉定理的一個特例，試推斷之。

定理：歐拉函數滿足\(\sum_{d | n} \varphi(d)=n\)，其中\(\sum\)的下标表示\(n\)的所有因數（包括\(n \text { 和 } 1\)）。

其它

生成元：群中元素可以由最小數目個群元的乘積生成，這組群元稱為該群的生成元，生成元的數目為有限群的秩。

秩：生成元的數目為有限群的秩。有限群的生成元的選擇不唯一，但秩不變。

群、環、域：

1. 群是含一個二進制運算，由機關元和逆元，而交換群（加群）是還要滿足交換律，半群是群的擴充，隻滿足結合律
2. 環是兩個二進制運算、對加法構成加群，對乘法構成半群，滿足配置設定律
3. 域是兩個二進制運算，對加法構成加群，對乘法構成非零元的交換群，滿足配置設定律

轉載請注明本文出處：https://www.cnblogs.com/newton/p/11664465.html