# 取模运算

## 模的概念
“模”指的是一个计量系统的计数范围，最常见的例子是时钟，它的计数范围为12个整点，所以其模为12。
数字电路里的计数器也是一个常见例子，一个8位计数器，其模为$2^8$，计数范围$[0,2^8-1]$。

## 取模运算定义
取模运算本质上是求取计量系统没有“溢出来”的量，即余数。

(我一般用碗盛锅里的饭来形象的思考这个过程，模数为碗的容量)

对于两个整数$a$和$b$，以及正整数$r$，模运算可以表示为：
$$ a\mod m = r $$
其中$r$是$a$除以$m$的余数，满足 $0 \leq r < m$

## 基本性质
* 同余关系
如果 $a \equiv b \mod m$，则$a$和$b$在模$m$下是同余的，意味着$(a-b)$是$m$的倍数。

* 加法性质
对于任意整数 ( a, b ) 和正整数 ( m )：
$$
(a + b) \mod m = [(a \mod m) + (b \mod m)] \mod m
$$

* 减法性质
对于任意整数 ( a, b ) 和正整数 ( m )：
$$
(a - b) \mod m = [(a \mod m) - (b \mod m) + m] \mod m
$$
（加上 ( m ) 是为了确保结果为非负数）

* 乘法性质
对于任意整数 ( a, b ) 和正整数 ( m )：
$$
(a \cdot b) \mod m = [(a \mod m) \cdot (b \mod m)] \mod m
$$

* 幂运算性质
对于任意整数 ( a ) 和正整数 ( m )，以及非负整数 ( k )：
$$
(a^k) \mod m = [(a \mod m)^k] \mod m
$$

* 逆元
在模 ( m ) 的运算中，如果存在整数 ( b ) 使得：
$$ a \cdot b \equiv 1 \mod m $$
则称 ( b ) 为 ( a ) 的模 ( m ) 逆元。逆元存在的条件是 ( a ) 和 ( m ) 互质（即它们的最大公约数为 1）。

* 分配律
模运算遵循分配律：
$$
a \cdot (b + c) \mod m = (a \cdot b \mod m + a \cdot c \mod m) \mod m
$$

* 结合律
模运算也遵循结合律：
- 加法结合律：
$$
(a + (b + c)) \mod m = ((a + b) + c) \mod m
$$
- 乘法结合律：
$$
(a \cdot (b \cdot c)) \mod m = ((a \cdot b) \cdot c) \mod m
$$

* 其他性质
如果 $( a \equiv b \mod m )$ 且 $( c \equiv d \mod m )$，则有：
$( a + c \equiv b + d \mod m )$
$( a - c \equiv b - d \mod m )$
$( a \cdot c \equiv b \cdot d \mod m )$