北邮《信息安全数学基础》：同余、剩余类与欧拉函数详解
北邮《信息安全数学基础》：同余、剩余类与欧拉函数详解
本文主要介绍了北邮《信息安全数学基础》课程中的同余相关知识点，包括同余的概念及基本性质、剩余类及完全剩余系、简化剩余系与欧拉函数、三大定理（欧拉定理、费马小定理、Wilson定理）以及模重复平方计算法等内容。这些内容对于理解信息安全数学基础非常重要。
一、同余的概念及基本性质
1、概念
正整数m，如果
则
2、定理
（1）
（2）①自反性
②对称性 若
则
③传递性 若
，
则
（3）
（4）若
则①
②
例、今天是星期五，那么
天后时星期几？
解：
所以
故是星期三。
（5）
①
②
例、n=637693，因为6+3+7+6+9+3=30（就是把n每位上的数加起来），
，所以
。
（6）
例、
（7）
（8）
（9）
（10）
（11）
（12）
二、剩余类及完全剩余系
定理
（1）设m是一个正整数，则
①任一整数必包含在一个 Cr 中，0 ≤ r < m-1
②
③
2、定义
Ca叫做模m的a的剩余类。
一个剩余类中的任一数叫该类的剩余或代表元。
若
共m个整数，并且其中任何两个数都不在同一剩余类，则
叫模m的一个完全剩余系。
3、定理
（2）
是模m的一个完全剩余系
他们模m两两不同余
例、
最小非负完全剩余系0,1,...,m-1
最小正完全剩余系1,2,...,m
最大非正完全剩余系-(m-1),...,-1,0
最大负完全剩余系-m,...,-1
绝对值最小完全剩余系
m偶 -m/2,-(m-2)/2,...,-1,0,1,...,(m-2)/2或 -(m-2)/2,...,-1,0,1,...,(m-2)/2,m/2
m奇 -(m-1)/2,...,-1,0,1,...,(m-1)/2
（3）（a，m）= 1，若k是遍历模m的一个完全剩余系，则对于任意b，ak+b也是
（4）m1，m2互素，k1，k2分别遍历m1，m2的完全剩余系，则m2·k1+m1·k2遍历m1·m2
例、
例、m1 = 2，m2 = 5，求 k3 遍历 m1·m2
解：k3 = k1·m2 + k2·m1
故k3 = 0,2,4,6,8,5,7,9,1,3
三、简化剩余系与欧拉函数
1、欧拉函数
（1）定义
：m个正整数 0,1,...,m-1 中与m互素的整数个数。
注：p为素数，则
（！！！！这个很重要，经常会用到！！！！）
（2）定理
对于素数幂
，有
2、简化剩余类与简化剩余系
（1）定义
一个模m的剩余类叫做简化剩余类，如果该类中存在一个与m互素的剩余，这时，简化剩余类中的剩余叫做简化剩余。
注：①简化剩余类的定义与剩余的选取无关
②两个简化剩余的乘积仍为简化剩余
（2）定理
②
是同一模m剩余类的两个剩余，则
（3）定义
在模m的所有不同简化剩余类中，从每个类中任取一个数组成的集合，叫做模m的一个简化剩余系。
例、设正整数m，则：
最小非负完全剩余系 0,1,...,m-1中与m互素的整数
最小正完全剩余系 1,2,...,m中与m互素的整数
最大非正完全剩余系 -(m-1),...,-1,0中与m互素的整数
最大负完全剩余系 -m,...,-1中与m互素的整数
绝对值最小完全剩余系
m偶 -m/2,-(m-2)/2,...,-1,0,1,...,(m-2)/2中与m互素的整数
或 -(m-2)/2,...,-1,0,1,...,(m-2)/2,m/2中与m互素的整数
m奇 -(m-1)/2,...,-1,0,1,...,(m-1)/2中与m互素的整数
（4）定理
④若 (a,m) = 1，k 是遍历模 m 的一个简化剩余系，则 ak 也是。
例、
⑤若 (a,m) = 1，则存在一个 a'，1 ≤ a' < m 使
。
证明：
（这个证明很重要！！！！a' 的求法就是用贝祖等式求 s 即为 a' ）
例、已知 m = 737，a = 635，求 a'
解：
（这个方法可能会有点麻烦，如果大家有更好的方法，欢迎大家在评论区留言）
⑥ (m1,m2) = 1，如果 k1, k2 分别遍历模 m1, m2 的简化剩余系，则 m2k1 + m1k2 遍历 m1*m2
3、欧拉函数性质
（1）
（！！！！！这个公式超级超级超级无敌重要！！！！！）
需要注意的是，前提条件一定是 m, n 互素！！！！！
例、
（2） p, q 是不同素数，则
四、三大定理
1、欧拉定理
2、费马小定理
p为素数，有
推论：p为素数，则
3、Wilson定理
p为素数，则
例、计算
解：
五、模重复平方计算法
计算
该计算法较为复杂且计算量巨大，考试是不许使用计算器的，所以考的可能不大，但仍需了解，以备不时之需，一旦考了即使因数过大计算不出来，也可以把步骤写对，这样不会扣很多分。
六、总结
1、同余
同余的概念和一些定理在计算中也会用到，请掌握。
两个典型题为：
（1）今天是星期几，*天后是星期几。
这种题解决办法有很多，请至少掌握一种。
（2）给一个数，问你能不能被3，9，7，11整除。
2、剩余类和剩余系
给你一个数，让你写出最小非负、最小正、最大非正、最大负、绝对值最小。
3、欧拉函数概念及性质
两个重要性质在计算中经常用到，请务必熟练，考试一定会涉及到。
4、三大定理
欧拉、费马小（尤其是推论）经常会用到，请一定要掌握，Wilson也有考的可能性，就一个简单的公式还是记住吧。需要注意的是，三大定理的证明也是考点，但由于篇幅有限和忙着课程就没有呈现，在此向大家抱歉，如果时间充足的话请自行翻阅教材查看证明过程，最好能自己证一遍，记忆会很深刻，也有助于对知识更深刻理解。
本文原文来自CSDN博客