2.4　模运算

2.4.1　模运算定义

模运算也称同余理论（Congruence），由24岁的高斯在他的著作《算术研究》中首次提出。模运算得到的结果其实就是除法定理中的余数。在除法定理中，如果用2去除一个正整数，很容易知道余数就只有两个，即0和1 ，其中偶数的余数是0 ，奇数的余数是1 。如果用3去除一个正整数，余数就只有3个，即0、1、2。模运算对除法定理的商不感兴趣，甚至熟悉一些式子后可以忽略，而感兴趣的是余数。

日常生活当中其实就有很多模运算的实际应用。例如，时间上的“星期”也就是关于模7的运算。大部分人都只对今天是星期几（余数）感兴趣，很少人对今天是今年的第几周(商)感兴趣。如果扩大范围，则所有只对周期性结果感兴趣的事情都是模运算。下面了解模运算的定义。

定义2.4.1　模运算

设，是一个定值且。规定当时，模同余。记作：

模运算拥有以下几个性质[8]。

1）反身性。对于所有的，都有。

2)对称性。对于所有的，都有。

3)传递性。对于所有的，如果且，那么。

对于，，并且和，那么：

●

●

●

●

● 如果，

例2.4.1　模运算例子。

在Python中，可以使用进行模运算，如。

例2.4.2　求。

解：。阶乘的增长非常可怕，如果没有模运算的帮助，解这道题非常困难。

不过由于，因此对于，都有：

也就是说：

给定，，如果，那么对于线性同余方程有且只有唯一解。如果，方程则可能有或没有解。如何求解方程？过程也非常简单，首先验证是否可以整除，如果不可以，则无解。如果可以，则用下面的方程进行求解。

将式子转化成，记作。使用欧几里得算法得到式子的解，调整得到。因此最后的解就是。

例2.4.3　求方程和。

解：第1个方程比较简单，很容易得到。该解是模情况下的唯一解，如果扩展至模，则是另一个解。

求第2个方程，由于，可以整除5 ，因此有且只有唯一解。然后计算，计算过程和例2.3.3相同，得到结果。所以该方程最小正剩余。

其实可以发现，无论模数多大，得到的值总是小于。因此模运算可以被看作一个环（Ring），也称为整数模的环（关于环的定义见2.9.2节），余数在这个环中怎么都跳不出去，最大值是。记作：

除此之外，当时，那么就会存在一个关于的逆元，使得。注意在模运算中，。下面通过一个例子来了解如何计算。

例2.4.4　设模数，。求。

解：很明显，因为它们都是素数。因此必有。由于，所以。

同理，如果，，那么。

因此规定，如果整数存在模的逆元，当且仅当。记作

也叫整数模乘法群（单位群），该群是数论的基础，在密码学中有非常重要的作用，特别是在素性测试中运用甚广。

例2.4.5　求和。

解：因为11是素数，所以都与11互素，因此很容易得到：

24是一个合数，所以小于24的其他合数都不是它的整数模的单位，因此只能从小于24的素数中选择。而3是24的一个因子，因此需要排除3 。经过相似步骤，最后可得: