4.5 欧拉定理和费马小定理

数学学习 · 爱知数学讲义

18
本章目录 · 1 节

本章导读

欧拉函数 定义为 中与正整数 互素的元素个数。。素数 满足 ,而合数 的欧拉函数小于 。

【例4.5.1】由素因子分解 求 。

解:把1至 中被 整除的数构成集合 ;与 不互素恰好表示属于这些集合中的至少一个。,,一般交集同理。由容斥并整理成乘积,得到

例如 ,。互素元素为1、7、11、13、17、19、23、29、31、37、41、43、47、49、53、59。公式对 可解释为空乘积为1,仍得到1。

定理4.5.1(欧拉定理):若 ,则 。证明:设 为所有与 互素的剩余类代表。乘 后仍与 互素,而且模 不会重复,因为 可消去;于是它们恰为原代表集合的一次排列。两组乘积同余,得到 。乘积本身也与 互素,故能消去,得到结论。证明中两次消去都依赖互素条件,不能省略。

定理4.5.2(费马小定理):素数 与整数 互素时,,这是欧拉定理在 下的特例。等价的另一形式是对任意整数 ,都有 ;当 时这一形式两侧都同余于0,所以不再要求互素。

费马小定理可以判定部分合数,但其逆命题不成立。例如 ,因此9一定不是素数;然而某个底数测试通过,不代表待测数必为素数。甚至存在对所有互素底数都通过的合数,例如561。因此不能把一个必要条件当成素性充分条件。教材后续RSA使用的是已满足条件时的欧拉、费马结论,不是用逆命题选择素数。