Aug 29, 2022 欧拉公式 欧拉函数在1~m中与m互素的整数的个数，记作𝜙(𝑚)𝜙(𝑚)={𝑎|1≤𝑎≤𝑚,gcd(𝑎,𝑚)=1}显然，𝜙(1)=0,𝜙(𝑝)=𝑝−1欧拉公式若gcd(𝑎,𝑚)=1，则𝑎𝜙(𝑚)≡1(mod𝑚).证明先来说明一个引理引理 令数列1≤𝑏1<𝑏2<…<𝑏𝜙(𝑚)<𝑚是1~m中与m互素的𝜙(𝑚)个整数。若𝑔𝑐𝑑(𝑎,𝑚)=1，则数列𝑏1𝑎,𝑏2𝑎,𝑏3𝑎,…,𝑏𝜙(𝑚)𝑎(mod𝑚),于数列1,2,3,…,𝑏𝜙(𝑚)(mod𝑚),相同（忽略次序）。引理证明证明过程与费马小定理证明过程类似。注意到𝑔𝑐𝑑(𝑏𝑖,𝑚)=𝑔𝑐𝑑(𝑎,𝑚)=1，则𝑔𝑐𝑑(𝑏𝑖𝑎,𝑚)=1.从而数列(1)与同余于数列(2)每一个数。这两个数列都含有𝜙(𝑚)个数字。从数列(1)中任取两个数𝑏𝑗𝑎和𝑏𝑘𝑎，假设它们同余：𝑏𝑗𝑎≡𝑏𝑘𝑎(mod𝑝)则𝑝|(𝑗−𝑘)𝑎，又因为𝑎≢0(mod𝑚)，所以𝑚|(𝑏𝑗−𝑏𝑘)。而1≤𝑏𝑗,𝑏𝑘≤𝑚−1，则 0≤|𝑏𝑗−𝑏𝑘|≤𝑚−2，仅有𝑏𝑗=𝑏𝑘时，𝑝|0。所以，𝑏1𝑎,𝑏2𝑎,𝑏3𝑎,…,𝑏𝜙(𝑚)𝑎模m不同余。𝜙(𝑚)个数模m不同余，这𝜙(𝑚)个余数一定就是数列(2)。得证。证明欧拉公式引理中的两个数列连乘得：𝑏1𝑎⋅(𝑏2𝑎)…⋅𝑏𝜙(𝑚)𝑎≡𝑏1⋅𝑏2…⋅𝑏𝜙(𝑚)(mod𝑚)即𝑎𝜙(𝑚)𝐵≡𝐵(mod𝑚)又有𝐵与𝑚互素，两边消掉得𝑎𝜙(𝑚)≡1(mod𝑚)得证。卡歇米尔数如果对于每个满足gcd(𝑎,𝑚)=1的整数a，同余式𝑎𝑚−1≡1(mod𝑚)成立，则称合数m为卡歇米尔数。例如𝑚=561=3*11*17是卡歇米尔数。