欧拉定理 (数论)

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

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

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

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

例子[编辑]

首先看一个基本的例子。令,此两数為互質正整數。小於等於5的正整数中与5互質的数有4個(1、2、3和4),所以(详情见欧拉函数)。计算:,与定理结果相符。

使用本定理可大程度地简化幂的模运算。比如计算的个位数時,可將此命題視為求被10除的余数:因7和10互質,且,故由欧拉定理可知。所以

一般在简化幂的模运算的时候,当互質時,可对的指数取模

,其中

证明[编辑]

一般的证明中会用到“所有与互質的同余类构成一个”的性质,也就是说,设是比 小的正整数中所有与 互素的数对应的同余类组成的集合(这个集合也称为模n简化剩余系)。这些同余类构成一个群,称为整数模n乘法群。所以当对这些数进行变换 的时候(是和互素的一个数,从而也属于某个同余类),变换所得的同余类集合仍然是原来的。即是说,集合相同。因此,。从而

素数的时候,,所以欧拉定理变为:

这就是费马小定理

参看[编辑]

参考书籍[编辑]

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