欧拉公式

欧拉函数

在1~m中与m互素的整数的个数，记作

显然，

欧拉公式

若，则

证明

先来说明一个引理

引理 令数列

是1~m中与m互素的个整数。

若，则数列

于数列

相同（忽略次序）。

引理证明

证明过程与费马小定理证明过程类似。

注意到，则.

从而数列(1)与同余于数列(2)每一个数。这两个数列都含有个数字。

从数列(1)中任取两个数和，假设它们同余：

则，又因为，所以。

而，则 ，仅有时，。

所以，模m不同余。

个数模m不同余，这个余数一定就是数列(2)。得证。

证明欧拉公式

引理中的两个数列连乘得：

即

又有与互素，两边消掉得

得证。

卡歇米尔数

如果对于每个满足的整数a，同余式成立，则称合数m为卡歇米尔数。

例如是卡歇米尔数。