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 。经过相似步骤，最后可得:
