符号与约定
- 未知数 均为质数。
- 其中 。
- 表示集合 和集合 在模 意义下相等。
定义
若 整数 和整数 除以正整数 的余数相等,则称 和 模 同余,记为 。
同余类与剩余系
对于 ,集合 的所有数模 同余,余数都是 ,该集合称为一个模 的同于类,简记为 。
模 的同余类一共有 个,分别为 。它们构成 的完全剩余系。
中与 互质的数代表的同余类有 个,它们构成 的简化余系。例如,模 的简化剩余系为 。
显然,简化同余系关于模 乘法封闭。
欧拉定理
对于 ,当 时有:
证明1:
设 其中 ,显然这个集合包含了所有比 小且与 互质的数。令 其中 。假设 时有 ,则有:
因为 ,所以有
因为 ,所以出现矛盾,假设不成立。
所以
所以有:
因为
所以有
证毕。
证明2:
设 ,则小于 且与 互质的集合著称集合 ,设二元运算 ,则代数系统 满足:
-
封闭性:因为 ,显然满足封闭性。
-
结合律:显然。
-
存在单位元
-
,(逆元)必定存在。
综上,该代数系统是群,且阶数为 ,根据拉格朗日定理::有限群的阶数是群中元素的阶数的整数倍,取任意 ,设 的阶数为 ,于是 ,证毕。
欧拉定理的推论
若 且 ,则对于任意正整数 有
证明:设 ,其中 ,即 。于是:
费马小定理
证明:
因为 为质数,所以有 ,显然 ,根据欧拉定理有:
证毕。
扩展欧拉定理
当 有:
当 时, ,显然成立。
当 时,设 ,只需证明对于每一个 都有 即可。
- 若 ,则有:
原因: 是积性函数。
- 若 ,则 必然是 的倍数,设 ,因为 ,易证 ,则 。
所以 ,所以有
综上,该定理成立。