欧拉定理 (数论)

维基百科,自由的百科全书
跳转至: 导航搜索

数论中,欧拉定理(也称费马-欧拉定理欧拉{\varphi}函数定理)是一个关于同余的性质。欧拉定理表明,若n,a为正整数,且n,a互素(即\gcd(a,n)=1),则

a^{\varphi(n)} \equiv 1 \pmod n

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

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

例子[编辑]

首先看一个基本的例子。令a = 3n = 5,这两个数是互素的。比5小的正整数中与5互素的数有1、2、3和4,所以\varphi(5)=4(详情见欧拉函数)。计算:a^{\varphi(n)} = 3^4 = 81,而81 \equiv 80 + 1 \equiv 1 \pmod{5} 。与定理结果相符。

这个定理可以用来简化幂的模运算。比如计算7^{222}的个位数,实际是求7^{222}被10除的余数。7和10互素,且\varphi(10)=4。由欧拉定理知7^4\equiv 1\pmod {10}。所以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}

一般地,在简化幂的模运算的时候,(当an互素) 我们要对a的指数取模\varphi(n)

x\equiv y \pmod {\varphi(n)},则a^x \equiv a^y \pmod n

证明[编辑]

一般的证明中会用到“所有与n互質的同余类构成一个”的性质,也就是说,设\left\{ \overline{a_1}, \overline{a_2}, \cdots , \overline{a_{\varphi(n)}} \right\}是比n 小的正整数中所有与n 互素的数对应的同余类组成的集合(这个集合也称为模n简化剩余系)。这些同余类构成一个群,称为整数模n乘法群。所以当对这些数进行变换\pi_a : \overline{a_i} \longmapsto \overline{a \cdot a_i} = \overline{a} \cdot \overline{a_i} 的时候(a是和n互素的一个数,从而也属于某个同余类),变换所得的同余类集合仍然是原来的\overline{a_1}, \overline{a_2}, \cdots , \overline{a_{\varphi(n)}}。即是说,集合\left\{ \overline{a_1}, \overline{a_2}, \cdots , \overline{a_{\varphi(n)}} \right\}\left\{ \overline{a a_1}, \overline{a a_2}, \cdots , \overline{a a_{\varphi(n)}} \right\}相同。因此,a^{\varphi(n)} a_1 a_2 \cdots a_{\varphi(n)} \equiv (a a_1)(a a_2) \cdots (a a_{\varphi(n)}) \equiv a_1 a_2 \cdots a_{\varphi(n)} \pmod n。从而a^{\varphi(n)} \equiv 1 \pmod n

n素数的时候,\varphi(n) =n -1 ,所以欧拉定理变为:

a^{n - 1} \equiv 1 \pmod n
a^{n} \equiv a \pmod n

这就是费马小定理

参看[编辑]

参考书籍[编辑]

  • 潘承洞 潘承彪. 《初等数论》. 北京大学出版社. 2003. ISBN 9787301060759. 
  • Albert H. Beiler 著,谈祥柏 译. 《数论妙趣--数学女王的盛情款待》. 上海教育出版社. 1998. ISBN 9787532054732.