取模和取余¶

取模和取余的区别¶

取模和取余都可以表示取出被除数和除数做除法运算时的余数，在除数和被除数都是正整数时，二者基本没有区别，但是如果被除数是负数，而二者就会有很大的区别

对于两个整数\(a\)和\(b\)来说，总是可以写成\(a = k \cdot b + r\)，其中\(k\)为任意整数，\(r\)为余数。所以对于整数\(a\)和\(b\)来说，取模运算和取余运算的方法都是按照下面的步骤进行：

1. 求商：\(c = a / b\)
2. 计算模或者余数：\(r = a - c \cdot b\)

在上面的两步中，取模和取余的不同就在于第一步：

1. 对于取模运算来说：求商意味着调用向下取整floor()函数（向不大于c的方向舍入），所以获取到的\(c\)应为floor(c)
2. 对于求余运算来说：求商意味着调用向上取整ceil()函数（向0方向舍入），所以获取到的\(c\)应为ceil(c)

例如，对于两个整数\(a = -7\)以及\(b = 4\)来说，取模和取余可以用下面的代码演示结果：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

#include <iostream>
#include <cmath>

using namespace std;

int main()
{
    // 取模和取余
    // 取模：a % b = a - b * floor(a / b)
    // 取余：a % b = a - b * ceil(a / b)

    cout << -7.0 / 4 << endl; // -1.75
    cout << floor(-7.0 / 4) << endl; // -2
    cout << ceil(-7.0 / 4) << endl; // -1

    cout << -7 % 4 << endl; // -3

    // 取模
    cout << -7 - 4 * floor(-7.0 / 4) << endl; // 1
    // 取余
    cout << -7 - 4 * ceil(-7.0 / 4) << endl; // -3

    return 0;
}

下面观察不同的编程语言对于取模和求余的定义

1
2
3
4
5
6
7
8

#include <iostream>
using namespace std;

int main()
{
    cout << -7 % 4 << endl;
    return 0;
}

1
2
3
4
5

public class mod {
    public static void main(String[] args) {
        System.out.println(-7 % 4); // -3
    }
}

1

console.log(-7 % 4); // -3

1

print(-7 % 4) # 1

上面的代码中可以看到，对于C/C++、Java和JavaScript来说，%意味着取余，对于Python来说，%意味着取模

同余定理¶

同余（英语：Congruence modulo，符号：\(≡\)）在数学中是指数论中的一种等价关系。当两个整数除以同一个正整数，若得相同余数，则二整数同余。同余是抽象代数中的同余关系的原型。最先引用同余的概念与\(≡\)符号者为德国数学家高斯

对于任意两个整数\(a\)和\(b\)来说，如果二者除以某一个正整数\(m\)所得的余数相等，则称\(a\)和\(b\)同余。具体来说，若存在一个整数\(k\)使得下面的等式成立：

则称\(a\)和\(b\)对于正整数\(m\)来说是同余的，一般记作：

例如，对于两个整数-4和1来说，对正整数5取模时可以表示为：\(\frac{-4 - 1}{5} = -1\)，因为\(-1\)是整数，满足对\(k\)的定义，所以说\(-4 ≡ 1\text{ }(mod \text{ }5)\)

根据同余定理\((a - b) / m = k\)，则有下面等式成立

取余运算修正¶

前面提到C/C++、Java和JavaScript语言，其%表示取余运算，所以在被除数为负数时，计算出的余数也为负数，但是大多数情况下都希望余数是整数（即Python中的取模运算结果），所以常会对取余运算的结果进行修正。以C++为例，假设a和b分别代表被除数和除数，其中a<0, b>0，可以通过下面的方式进行修正：

1

(a % b + b) % b