求余运算（Remainder）

参考链接：余数 – 维基百科

自然数的余数

定义：如果$a$和$d$是两个自然数，$d$非零，可以证明存在两个唯一的整数$q$和$r$，满足 $a = qd + r$ 且$0\leq r < d$。其中，$q$被称为商，$r$被称为余数。

举例

• 13除以10，商为1，余数为3，13=1×10+3或13÷10=1…3。
• 26除以4，商为6，余数为2，26=6×4+2或26÷4=6…2。
• 56除以7，商为8，余数为0，56=8×7+0或56÷7=8。
• 9除以10，商为0，余数为9，9=0×10+9或9÷10=0…9。（当被除数小于除数时，我们以被除数为余数。）

一般整数的余数

如果$a$与$d$是整数，$d$非零，那么余数$r$满足这样的关系：$a = qd + r$，$q$为整数，且$0\leq |r| < |d|$。

可见，这样定义会导致两种可能的余数，例如出除法式子$-42 \over -5$可以表达为
$$
-42 = 9 \times (-5) + 3 （在数学工作者中使用较多）
$$
或
$$
-42 = 8 \times (-5) + (- 2)
$$
即余数可能是3或-2。

这种对余数不明确的定义可能导致严重的计算问题，对于处理关键任务的系统，错误的选择会导致严重的后果。因此对于不同的计算机编程语言，会有例如余数与被除数同号的规定。

负余数和正余数之间的转换

在上面的例子，负余数为正余数减5得来，5即是除数$d$。通常，当除以$d$时，如果正余数为$r_1$，负余数为$r_2$，那么
$$
r_2 = r_1 + d
$$

编程语言

python

python3语言定义，在不能整除的情况下，余数与除数同号，即$-42 \over -5$表达为
$$
-42 = 8 \times (-5) + (- 2)
$$
而$42 \over -5$表达为
$$
42 = (-9) \times (-5) + (- 3)
$$

C/C++

C/C++规定余数与被除数同号，即$-42 \over -5$表达为
$$
-42 = 8 \times (-5) + (- 2)
$$
而$42 \over -5$表达为
$$
42 = (-8) \times (-5) + 2
$$

实数的余数

当$a$和$d$是实数，且$d$非零，$a$除以$d$会得到另一个实数（商），没有所谓的剩余的数.但如果要求商为一个整数，则余数的概念还是有必要的。可以证明：存在唯一的整数商$q$和唯一的实数$r$使得：$a = q \times d + r$, 。$0\leq r < |d|$，同时在整数除法里，余数可以要求为负，即满足关系：$-|d| < r \leq 0$

如上在实数范围内扩展余数的定义在数学理论中并不重要；尽管如此，很多程序语言都实现了这个定义（参见同余）。

求模运算（Modulo）

参考链接：模除 – 维基百科

在数学中，取模运算的结果就是欧几里德除法(见文章目录)的余数。当然也有许多其他的定义方式。计算机和计算器有许多种表示和储存数字的方法，因此在不同的硬件环境下、不同的编程语言中，取模运算有着不同的定义。

几乎所有的计算系统中，$n$除$a$得到的商$q$和余数$r$均满足以下式子：
$$
q \in \mathbb{Z}；
a = n \times q + r；
|r| < |n|
$$
然而这样做，当余数非0时，余数的符号仍然是有歧义的：余数非0时，它的符号有两种选择，一个正、一个负。

通常情况下，在数论中总是使用正余数。但在编程语言中，余数的符号取决于编程语言的类型和被除数$a$或除数$b$的符号。

不同编程语言对整数取模运算的符号

运算律

这里只做简单介绍，详细说明见：模除 – 维基百科

模运算与基本四则运算有些相似，但是除法例外。其规则如下：

1. (a + b) % p = (a % p + b % p) % p
2. (a – b) % p = (a % p – b % p) % p
3. (a * b) % p = (a % p * b % p) % p
4. a ^ b % p = ((a % p)^b) % p

结合律：

((a+b) % p + c) % p = (a + (b+c) % p) % p

((ab) % p * c)% p = (a * (bc) % p) % p

交换律：

(a + b) % p = (b+a) % p

(a * b) % p = (b * a) % p

分配律：

(a+b) % p = ( a % p + b % p ) % p

((a +b)% p * c) % p = ((a * c) % p + (b * c) % p) % p

【推论】

• 若a≡b (% p)，则对于任意的c，都有(a + c) ≡ (b + c) (%p)
• 若a≡b (% p)，则对于任意的c，都有(a * c) ≡ (b * c) (%p)
• 若a≡b (% p)，c≡d (% p)，则 (a + c) ≡ (b + d) (%p)，(a – c) ≡ (b – d) (%p)，(a * c) ≡ (b * d) (%p)

求余和取模小结

有人会把取模运算和求余运算分开解释，又采用特定的语言去举例，但是我个人认为这两种运算目标都是一致，只是求余运算倾向于数学，而取模运算倾向于计算机科学，之所以不同语言会有不同的结果，本质是因为根据求余运算定义导致余数不唯一时不同程序设计语言采用了不同的结果，但他们都会根据某种依据来给出唯一的结果。

例如204. 表达整数的奇怪方式 – AcWing题库

题目明确要求$0 \leq x$，那么就等于限定余数大于0，而通过上面的讲解，当使用C/C++时，得到的余数不一定大于0，因此使用负余数和正余数之间的转换(见文章目录)，将余数转为正数

欧几里得除法

带余除法，也称为欧几里德除法是数学中的一种基本算术计算方式。给定一个被除数$a$和一个除数$b$，带余除法给出一个整数$q$和一个介于一定范围的余数$r$，使得下面等式成立：
$$
a = q \times b + r
$$
一般限定余数$0\leq r<b$，也有限定在$-{b \over 2}$到${b \over 2}$之间。这样的限定都是为了使得满足等式的$q$有且仅有一个。这时候的称$q$为带余除法的商。带余除法一般表示为：
$$
a \div b = q …r
$$
表达为：“$a$除以$b$等于$q$，余$r$”。