查看“︁欧拉定理 (数论)”︁的源代码

{{NoteTA
|G1=Math
}}
{{no footnotes|time=2014-11-08T22:55:27+00:00}}{{Distinguish|欧拉定理 (几何)|欧拉方程}}在[[数论]]中，'''欧拉定理'''（也称'''费马-欧拉定理'''或'''欧拉<math>{\varphi}</math>函数定理'''）是一个关于同余的性质。欧拉定理表明，若<math>n,a</math>为正[[整数]]，且<math>n,a</math>[[互素|-{zh-hans:互素; zh-hant: 互質}-]]（即<math>\gcd(a,n)=1</math>），则
<center><math>a^{\varphi(n)} \equiv 1 \pmod n</math></center>

即<math>a^{\varphi(n)}</math>与1在模n下[[同余]]；[[φ]](n)为[[欧拉函数]]。欧拉定理得名于[[瑞士]][[数学家]][[莱昂哈德·欧拉]]。

欧拉定理实际上是[[费马小定理]]的推广。

== 例子 ==
首先看一个基本的例子。令<math>a = 3</math>，<math>n = 5</math>，此两数為[[互質]][[正整數]]。小於等於5的正整数中与5互質的数有4個（1、2、3和4），所以<math>\varphi(5)=4</math>（详情见[[欧拉函数]]）。计算：<math>a^{\varphi(n)} = 3^4 = 81 \equiv 1 \pmod{5} </math>，与定理结果相符。

使用本定理可大程度地简化幂的模运算。比如计算<math>7^{222}</math>的个位数時，可將此命題視為求<math>7^{222}</math>被10除的余数：因7和10互質，且<math>\varphi(10)=4</math>，故由欧拉定理可知<math>7^4\equiv 1\pmod {10}</math>。所以<math>7^{222}= 7^{4\cdot 55+2}= (7^4)^{55}\cdot 7^2\equiv 1^{55}\cdot 7^2\equiv 49\equiv 9\pmod{10}</math>。

一般在简化幂的模运算的时候，当<math>a</math>和<math>n</math>互質時，可对<math>a</math>的指数取模<math>\varphi(n)</math>：

<math>a^x \equiv a^y \pmod n</math>，其中<math>x\equiv y \pmod {\varphi(n)}</math>。

== 证明 ==

一般的证明中会用到“所有与<math>n</math>[[互質]]的同余类构成一个[[群]]”的性质，也就是说，设<math>\left\{ \overline{a_1}, \overline{a_2}, \cdots , \overline{a_{\varphi(n)}} \right\}</math>是比<math>n</math> 小的正整数中所有与<math>n</math> 互素的数对应的[[同余|同余类]]组成的集合（这个集合也称为模''n'' 的[[简化剩余系]]）。这些同余类构成一个群，称为'''[[整数模n乘法群]]'''。因为此群阶为<math> \varphi(n)</math>，所以<math>a^{\varphi(n)} \equiv 1 \pmod n</math>。

当<math>n</math>是[[素数]]的时候，<math>\varphi(n) =n -1 </math>，所以欧拉定理变为：
:<math>a^{n - 1} \equiv 1 \pmod n</math>或
:<math>a^{n} \equiv a \pmod n</math>

这就是[[费马小定理]]。

== 参看 ==
* [[初等数论]]
* [[欧拉定理]]
* [[欧拉函数]]
* [[同余]]
* [[群论]]
* [[RSA加密算法]]

== 参考书籍 ==
* {{cite book | title=《初等数论》 |author =潘承洞 潘承彪   | publisher =北京大学出版社 | year =2003 |isbn =9787301060759 }}
* {{cite book | title=《数论妙趣--数学女王的盛情款待》 |author = Albert H. Beiler 著，谈祥柏 译 | publisher =上海教育出版社 | year =1998 |isbn =9787532054732 }}
{{莱昂哈德·欧拉}}

[[Category:同余]]
[[Category:数论定理]]
[[Category:包含证明的条目]]
[[Category:莱昂哈德·欧拉]]