模运算和同余定理

Last Updated: 2023-06-11 13:05:16 Sunday

-- TOC --

本文总结数学中的模运算和同余定理。

模运算

给定两个正整数m，n，如果：

\(m \div n = a ... b\)

a是商，b是余数，b就是m模n的模运算结果，可以写成：

\(m \bmod n = b\)，模数n不能等于0.

基本上，模运算就是在计算除法的余数。

例如，13 mod 3 = 1 、27 mod 6 = 3 、28 mod 2 = 0

编程的时候，模运算的特性，在某些场景下，可以提高代码性能。比如，假设我们要将某个pointer在一个ring上移动offset的位置，offset可能很大，会绕ring好几圈，同时，offset可能是一个负数，表示反方向移动。此时，做一个模运算，可以有效提升性能。

假设ring长度为9：

>>> 5 % 9
5
>>> (5+9) % 9
5
>>> (5+9*12345) % 9
5

offset为负时：

>>> -4 % 9
5
>>> (-4-9) % 9
5
>>> (-4-9*12345) % 9
5

反方向移动4个位置，等同于正方向移动5个位置。

给定一个正整数m，如果两个整数a和b满足(a-b)能被m整除，即 \((a-b)\bmod m=0\)，那么就称整数a与b对模m同余，记作 \(a \equiv b(\bmod m)\)。（a与b在模m的时候恒等）

同余是两个数的性质，模运算是一种计算！

对模m同余的两个数，它们都是m的某个倍数再加上一个相同的“余数”。

同余定理有一些简单的结论：

for any integer n, \(n^2\) mod 3 or 4 can only be 0 or 1；对于任意整数n，\(n^2\) 模3或4的结果只能是0或1。
for any integer n, \(n^2\) mod 8 can only be 0 or 1 or 4；对于任意整数n，\(n^2\) 模8的结果只能是0或1或4。
for any positive integer n, \(n \equiv \text{sum of the digits of n} (\bmod 9)\)；对于任意正整数n，n与将n各位相加得到的和与9同余。

-- EOF --

-- MORE --