同余
§2.1同余的定义和基本性质定义1 给定一个正整数，如果，则称整数对模同余，记作；如果，则称整数对模不同余，记作。
从定义可以看出，任意的两个整数，要么，要么。结合整除的性质，我们很容易得到同余的两个等价定义：
（1）整数对模同余的充要条件是存在一个整数使得；
（2）整数对模同余的充要条件是用去除整数和所得的最小非负余数相同。
在同余式中，若，则称是对模的最小非负剩余，一般用来表示；若，则称是对模的最小正剩余；若，，则称是对模的绝对值最小剩余。
从关系的角度出发，我们很容易证明同余是一种等价关系，即同余满足如下性质：
性质1 （1）自反性：；
（2）对称性：；
（3）传递性：
。
同余其实就是整除的一种符号表示，因此我们在第一章中了解的整除的一些基本性质都可以用同余符号简单地表示。
性质2 （1） 若，，则
,
特别地，对于任意一个整数，都有
，；
（2）若，，则
；
（3）若，的公因数，则；
（4）若，，，则；
（5）若，是的最大公因数，则，进一步，若，则有；
（6）若，则，进一步，若是一个整系数多项式（即系数是整数，其中），则；
（7）同余式组同时成立的充要条件是
；
（8）。
利用上述关于同余的一些基本性质，我们可以得到检查因数的两个方法：
例1 证明：一个整数能被3或9整除的充要条件是它的十进位数码的和能被3或9整除。
证明：设是一个正整数。把写成十进位数的形式：
。
因为，所以，由此可知，当且仅当，对于9的情形同理可证。如：，，，所以3是的因数，9不是的因数。
例2 设
证明：能被7（或11，或13）整除的充要条件是7（或11，或13）整除。
证明：因为，即，所以，即有
，于是当且仅当，对于11、13的情形同理可证。
因为，所以在判断一个整数是否被11整除时用百进制更简单。
下面我们介绍一个很有名的称作弃九法的方法，它利用同余的性质来验算整数计算结果是否错误。这个方法对于加、减、乘都适用，为了简便，我们只给出普通乘法的证明。假设我们由普通乘法运算求出整数的乘积为，并且设
。
。
。
如果有
则所计算的结果是错误的。
按照例1，，，，由同余的性质当然可以得到，所以，若，则。
例3 设，，如果按照普通乘法计算得到的乘积是，那么按照上面的方法，，，但是，所以计算有误。
从上面的证明我们可以看出这种方法有一个缺陷，当使用弃九法时，得到的结果虽然是，也不能完全肯定原计算是正确的。如在上面例子中，如果有人计算出来的结果为4540485362，那么用弃九法得到，而并未检查出错误来，实际的乘积结果为4540485326。
2005年7月26日是星期二，问此天后第天是星期几？
解 依题意，我们需要求，即整数模7的最小非负剩余。
因为，所以
因此，第天是星期四。
现在我们利用同余的理论来计算某一特定的日子是星期几。例如，香港回归日1997年7月1日是星期几，或者中华人民共和国成立日是星期几？如果一年的天数可被7整除，那么所有的日期在每一年中总有相同的星期数，这样日历的编制将大大简化。但是，目前一年的天数是，而闰年的天数是，这表明，在平年一个给定日期的星期数在下一年要加1，碰到闰年这一规律就被破坏了。值得注意的是，目前国际通用的公历是教皇格里高利十三实行的。当时他召集了很多学者和僧侣讨论历法改革问题，决定采用业余天文学家利里奥的方案，每四百年去掉三个闰日，那些世纪数不能被4整除的世纪年不再算作闰年。
下面我们给出一个方便的计算公式，为此规定0代表星期日，1代表星期一，2代表星期二，3代表星期三，4代表星期四，5代表星期五，6代表星期六。注意到闰年所加的一天不在一年的开头，也不在一年的末尾，而是在2月的29日，因此我们可以做如下处理：约定3月为第一个月，第二年的2月作为第十二个月。如1997年7月1日要写成“1997年5月1日”，1997年1月1日要写成“1996年11月1日”。
假定有一个具体的日期（注意如下的公式和公式的证明都是经过处理后的时间）：第年月日。令（即为100除的最小非负余数），，如果用表示这一日期的星期数，则有如下计算公式：
如1997年7月1日要写成,1997年5月1日”，代入上式计算可得，因此1997年7月1日是星期二。
上述公式的证明：首先任取一年如2000年作为开始的一年，并且把这一年的1月1日（实际时间为3月1日）的星期数记为，下面来求第年1月1日的星期数。注意到平年的天数为365，且，每过一个平年，星期数将增加1，若不考虑闰年，则相应的第年1月1日的星期数为
闰年的天数为366，注意到闰年每4年一次，通常年数被4整除时是闰年，世纪年通常不是闰年，但当世纪数可被4整除时，第年仍然是闰年，所以需要对上述星期数增加如下修正项：
合在一起即为
再按模7简化后得到
2005年1月1日（实际为3月1日）是星期二，即，代入上式可以求出，即第年1月1日的星期数为
下面再来确定从1月1日到该年任意一日的星期数，注意每一月的1日（从1月开始）应该增加的星期数分别为0，3，5，8，10，13，16，18，21，23，26，29，每月的平均增长是2.6，所以个月的增长数应该为，通过修正被减项，我们可以得到正确的表达式为
这个月的第日的星期数应加上，因此最终第年月日的星期数为
密码学中有很多模运算，因为计算模的离散对数和平方根都很困难，即求解方程
和
很困难，它们的困难性将给密码体制的安全性带来保证。在计算机上做模运算要要容易一些，因为它能够限制中间值和结果的范围。对于模（位二进制），做加、减、乘和之间结果都不会超过位。在计算时，如果整数的值都比较小，直接先计算的值，然后对其进行求模运算。
求的十进制表示中的最后两位数字。
在模运算计算中，还有一类问题，常常要对大整数模和大整数，计算
如果按照普通的递归运算
，
对于大整数而言比较费时，须做次乘法，可以对其使用加速算法。常用的加速算法有两种，一种是减少乘法的次数，另一种是优化每次乘法。
如果将写成二进制：
，
其中，则模运算可以归纳为
模重复平方算法2.1.1：
（1）将写成二进制：
，
其中；
（2）令，，；
（3）令，，；
（4）如果，回到（3）；
（5）否则，输出的值，则有。
此算法至多需要进行次平方和次乘法。当然我们也可以对这个算法进行一些改进
模重复平方算法2.1.2：
1）将写成二进制：
，
其中；
（2）令， ；
（3）令，,；
（4）如果，回到（3）；
（5）否则输出的值，则有。
算法2.1.2和算法2.1.1执行同样数量的平方和乘法，不过，算法2.1.2是以一个固定的来做乘法。
对于模幂运算，有时候如果使用固定窗口算法或者滑动窗口算法，将会达到优化平方运算的目的，减少运算的复杂性。
首先我们简单的介绍一下固定窗口算法：为了计算，我们首先对指数进行一定的窗口处理，记，则可以进行如下二进制分块：
其中
，，
，若。
因此有
固定窗口模幂算法2.1.3
(1) 确定窗口的大小为，将按照上述方法给出如下二进制表示：
（2）令,，；
（3）令，,；
（4）如果，回到（3）；
（5）否则，
（ⅰ）如果；
（ⅱ）如果，则；
则有。
在对指数进行窗口处理过程中，如果允许窗口的值小于，同时保证窗口的最低位和最高位都必须是1，若窗口开始遇到0则跳过，从1开始启动窗口。这样可以减少乘法的次数。
滑动窗口模幂算法2.1.4
确定窗口的大小为，按照上述方法给出的二进制表示：
，其中的最低位和最高位都是1，的长度为，是全为0的块，块的长度为，的值可能为0；
（2）令,，；
（3）令,，，，；
（4）如果，回到（3）；
（5）则有。
例6 试用如上四种算法计算。
解 因为
算法2.1.1
，
，
，
，
，
，
，
，
，
，
，
，
，
，
，
，
从而。
算法2.1.2
，
，
，
，
，
，
，
，
，
，
，
，
，
，
，
，
从而。
算法2.1.3
设窗口大小为3，则有
，
，
，
，
，
从而。
算法2.1.4
设窗口大小为3，则有
，
，
，
，
从而。
§2.1同余的定义和基本性质定义1 给定一个正整数，如果，则称整数对模同余，记作；如果，则称整数对模不同余，记作。
从定义可以看出，任意的两个整数，要么，要么。结合整除的性质，我们很容易得到同余的两个等价定义：
（1）整数对模同余的充要条件是存在一个整数使得；
（2）整数对模同余的充要条件是用去除整数和所得的最小非负余数相同。
在同余式中，若，则称是对模的最小非负剩余，一般用来表示；若，则称是对模的最小正剩余；若，，则称是对模的绝对值最小剩余。
从关系的角度出发，我们很容易证明同余是一种等价关系，即同余满足如下性质：
性质1 （1）自反性：；
（2）对称性：；
（3）传递性：
。
同余其实就是整除的一种符号表示，因此我们在第一章中了解的整除的一些基本性质都可以用同余符号简单地表示。
性质2 （1） 若，，则
,
特别地，对于任意一个整数，都有
，；
（2）若，，则
；
（3）若，的公因数，则；
（4）若，，，则；
（5）若，是的最大公因数，则，进一步，若，则有；
（6）若，则，进一步，若是一个整系数多项式（即系数是整数，其中），则；
（7）同余式组同时成立的充要条件是
；
（8）。
利用上述关于同余的一些基本性质，我们可以得到检查因数的两个方法：
例1 证明：一个整数能被3或9整除的充要条件是它的十进位数码的和能被3或9整除。
证明：设是一个正整数。把写成十进位数的形式：
。
因为，所以，由此可知，当且仅当，对于9的情形同理可证。如：，，，所以3是的因数，9不是的因数。
例2 设
证明：能被7（或11，或13）整除的充要条件是7（或11，或13）整除。
证明：因为，即，所以，即有
，于是当且仅当，对于11、13的情形同理可证。
因为，所以在判断一个整数是否被11整除时用百进制更简单。
下面我们介绍一个很有名的称作弃九法的方法，它利用同余的性质来验算整数计算结果是否错误。这个方法对于加、减、乘都适用，为了简便，我们只给出普通乘法的证明。假设我们由普通乘法运算求出整数的乘积为，并且设
。
。
。
如果有
则所计算的结果是错误的。
按照例1，，，，由同余的性质当然可以得到，所以，若，则。
例3 设，，如果按照普通乘法计算得到的乘积是，那么按照上面的方法，，，但是，所以计算有误。
从上面的证明我们可以看出这种方法有一个缺陷，当使用弃九法时，得到的结果虽然是，也不能完全肯定原计算是正确的。如在上面例子中，如果有人计算出来的结果为4540485362，那么用弃九法得到，而并未检查出错误来，实际的乘积结果为4540485326。
2005年7月26日是星期二，问此天后第天是星期几？
解 依题意，我们需要求，即整数模7的最小非负剩余。
因为，所以
因此，第天是星期四。
现在我们利用同余的理论来计算某一特定的日子是星期几。例如，香港回归日1997年7月1日是星期几，或者中华人民共和国成立日是星期几？如果一年的天数可被7整除，那么所有的日期在每一年中总有相同的星期数，这样日历的编制将大大简化。但是，目前一年的天数是，而闰年的天数是，这表明，在平年一个给定日期的星期数在下一年要加1，碰到闰年这一规律就被破坏了。值得注意的是，目前国际通用的公历是教皇格里高利十三实行的。当时他召集了很多学者和僧侣讨论历法改革问题，决定采用业余天文学家利里奥的方案，每四百年去掉三个闰日，那些世纪数不能被4整除的世纪年不再算作闰年。
下面我们给出一个方便的计算公式，为此规定0代表星期日，1代表星期一，2代表星期二，3代表星期三，4代表星期四，5代表星期五，6代表星期六。注意到闰年所加的一天不在一年的开头，也不在一年的末尾，而是在2月的29日，因此我们可以做如下处理：约定3月为第一个月，第二年的2月作为第十二个月。如1997年7月1日要写成“1997年5月1日”，1997年1月1日要写成“1996年11月1日”。
假定有一个具体的日期（注意如下的公式和公式的证明都是经过处理后的时间）：第年月日。令（即为100除的最小非负余数），，如果用表示这一日期的星期数，则有如下计算公式：
如1997年7月1日要写成,1997年5月1日”，代入上式计算可得，因此1997年7月1日是星期二。
上述公式的证明：首先任取一年如2000年作为开始的一年，并且把这一年的1月1日（实际时间为3月1日）的星期数记为，下面来求第年1月1日的星期数。注意到平年的天数为365，且，每过一个平年，星期数将增加1，若不考虑闰年，则相应的第年1月1日的星期数为
闰年的天数为366，注意到闰年每4年一次，通常年数被4整除时是闰年，世纪年通常不是闰年，但当世纪数可被4整除时，第年仍然是闰年，所以需要对上述星期数增加如下修正项：
合在一起即为
再按模7简化后得到
2005年1月1日（实际为3月1日）是星期二，即，代入上式可以求出，即第年1月1日的星期数为
下面再来确定从1月1日到该年任意一日的星期数，注意每一月的1日（从1月开始）应该增加的星期数分别为0，3，5，8，10，13，16，18，21，23，26，29，每月的平均增长是2.6，所以个月的增长数应该为，通过修正被减项，我们可以得到正确的表达式为
这个月的第日的星期数应加上，因此最终第年月日的星期数为
密码学中有很多模运算，因为计算模的离散对数和平方根都很困难，即求解方程
和
很困难，它们的困难性将给密码体制的安全性带来保证。在计算机上做模运算要要容易一些，因为它能够限制中间值和结果的范围。对于模（位二进制），做加、减、乘和之间结果都不会超过位。在计算时，如果整数的值都比较小，直接先计算的值，然后对其进行求模运算。
求的十进制表示中的最后两位数字。
在模运算计算中，还有一类问题，常常要对大整数模和大整数，计算
如果按照普通的递归运算
，
对于大整数而言比较费时，须做次乘法，可以对其使用加速算法。常用的加速算法有两种，一种是减少乘法的次数，另一种是优化每次乘法。
如果将写成二进制：
，
其中，则模运算可以归纳为
模重复平方算法2.1.1：
（1）将写成二进制：
，
其中；
（2）令，，；
（3）令，，；
（4）如果，回到（3）；
（5）否则，输出的值，则有。
此算法至多需要进行次平方和次乘法。当然我们也可以对这个算法进行一些改进
模重复平方算法2.1.2：
1）将写成二进制：
，
其中；
（2）令， ；
（3）令，,；
（4）如果，回到（3）；
（5）否则输出的值，则有。
算法2.1.2和算法2.1.1执行同样数量的平方和乘法，不过，算法2.1.2是以一个固定的来做乘法。
对于模幂运算，有时候如果使用固定窗口算法或者滑动窗口算法，将会达到优化平方运算的目的，减少运算的复杂性。
首先我们简单的介绍一下固定窗口算法：为了计算，我们首先对指数进行一定的窗口处理，记，则可以进行如下二进制分块：
其中
，，
，若。
因此有
固定窗口模幂算法2.1.3
(1) 确定窗口的大小为，将按照上述方法给出如下二进制表示：
（2）令,，；
（3）令，,；
（4）如果，回到（3）；
（5）否则，
（ⅰ）如果；
（ⅱ）如果，则；
则有。
在对指数进行窗口处理过程中，如果允许窗口的值小于，同时保证窗口的最低位和最高位都必须是1，若窗口开始遇到0则跳过，从1开始启动窗口。这样可以减少乘法的次数。
滑动窗口模幂算法2.1.4
确定窗口的大小为，按照上述方法给出的二进制表示：
，其中的最低位和最高位都是1，的长度为，是全为0的块，块的长度为，的值可能为0；
（2）令,，；
（3）令,，，，；
（4）如果，回到（3）；
（5）则有。
例6 试用如上四种算法计算。
解 因为
算法2.1.1
，
，
，
，
，
，
，
，
，
，
，
，
，
，
，
，
从而。
算法2.1.2
，
，
，
，
，
，
，
，
，
，
，
，
，
，
，
，
从而。
算法2.1.3
设窗口大小为3，则有
，
，
，
，
，
从而。
算法2.1.4
设窗口大小为3，则有
，
，
，
，
从而。
