欧拉函数
欧拉于18世纪提出的数论函数
条目
历史版本
1760年，瑞士数学家莱昂哈德·欧拉（Leonhard Euler）[2]证明了费马定理，同年，提出了关于表示所有不大于n且与n互素的正整数个数的问题。[1]1770年，柏林出版社出版了欧拉的数论专著《代数指南》(Anleitung zur algebra)，该函数被收入书中。1801年，高斯(Gauss)将其命名为欧拉函数。[1]
欧拉函数有一些基本性质，如欧拉函数是积性函数，但不是完全积性函数。[1][4][5]与其相关的概念是简化剩余系，[6]欧拉定理是费马小定理对于欧拉函数的推广。[7]欧拉函数在数论、加密学方面应用广泛，如RSA算法是按照欧拉函数性质设计而来。[4][3]
这个函数不仅在数论中有着重要的地位，也在现代密码学中扮演着关键角色，尤 其是在RSA加密算法的设计中。欧拉函数实际上是模n的同余类所构成的乘法群的阶，这个性质与拉格朗日定理一起构成了欧拉定理的证明基础。