1 简介

模算术，通常称为 “mod”或“modulo”，是一种 数学运算，当一个整数除以 另一个整数时求出余数。它 广泛应用于 计算机科学、密码学和算法设计。

定义和公式

给定两个整数 A（被除数）和 B（除数）， 模运算定义为：

		A 与 B = R

其中 R 是 A 除以 B 时的余数。这可以 表示为：

		A = B * Q + R

Q 是 商（整数除法结果）。

R 为余数，满足 0 ≤ R < |B|。

例如：

    7 mod 3 = 1 （7 = 3 * 2 + 1）
    -7 mod 3 = 2（因为 余数必须为非负数）

2 代码实现

下面用 Golang 和 Python 给出若干示例：模加/模乘、扩展欧几里得求逆、快速幂、解一元线性同余方程、以及中国剩余定理（CRT）。

1. Golang 示例（可直接 go run）

基本模运算（非负结果）

    func mod(a, m int64) int64 {
        r := a % m
        if r < 0 {
            r += m
        }
        return r
    }

    func addMod(a, b, m int64) int64 {
        return mod(a+b, m)
    }

    func mulMod(a, b, m int64) int64 {
        return mod((a% m) * (b % m), m)
    }

扩展欧几里得：返回 (g, x, y) 使 ax + by = g

    func extGcd(a, b int64) (int64, int64, int64) {
        if b == 0 {
            return a, 1, 0
        }
        g, x1, y1 := extGcd(b, a%b)
        // x = y1, y = x1 - (a/b)*y1
        x := y1
        y := x1 - (a/b)*y1
        return g, x, y
    }

模逆（若不存在返回 (0,false)）

    func modInv(a, m int64) (int64, bool) {
        g, x, _ := extGcd(a, m)
        if g != 1 && g != -1 { // gcd != 1 无逆
            return 0, false
        }
        // x 可能为负
        inv := mod(x, m)
        return inv, true
    }

快速幂（模幂）

    func powMod(base, exp, modn int64) int64 {
        base = mod(base, modn)
        var res int64 = 1
        for exp > 0 {
            if exp&1 == 1 {
                res = mulMod(res, base, modn)
            }
            base = mulMod(base, base, modn)
            exp >>= 1
        }
        return res
    }

解线性同余 a * x ≡ b (mod n) 返回 (hasSolution, x0, mod) 其中解集合为 x ≡ x0 (mod mod/g)

    func solveLinearCongruence(a, b, n int64) (bool, int64, int64) {
        g, x, _ := extGcd(a, n)
        if b%g != 0 {
            return false, 0, 0
        }
        // a*x0 ≡ b (mod n) -> multiply x by b/g
        x0 := mod(x*(b/g), n)
        return true, x0, n / g
    }

中国剩余定理（pairwise coprime）

    // input: residues r[i], moduli m[i]（互质）
    // return (x, M) where x is solution modulo M = prod(m)
    func crt(res []int64, mods []int64) (int64, int64, bool) {
        if len(res) != len(mods) || len(res) == 0 {
            return 0, 0, false
        }
        // naive pairwise check omitted for brevity (assume coprime)
        M := int64(1)
        for _, mi := range mods {
            M *= mi
        }
        var x int64 = 0
        for i := range res {
            mi := mods[i]
            Mi := M / mi
            inv, ok := modInv(Mi, mi)
            if !ok {
                return 0, 0, false
            }
            term := mulMod(mulMod(res[i], Mi, M), inv, M)
            x = (x + term) % M
        }
        return mod(x, M), M, true
    }

使用方式

    func main() {
        fmt.Println("模运算示例:")
        fmt.Println("7 + 10 mod 12 =", addMod(7, 10, 12))
        fmt.Println("7 * 10 mod 12 =", mulMod(7, 10, 12))

        // 模逆示例
        if inv, ok := modInv(3, 11); ok {
            fmt.Println("3 的模 11 逆是", inv) // expect 4
        } else {
            fmt.Println("无逆")
        }

        // 快速幂
        fmt.Println("2^100 mod 13 =", powMod(2, 100, 13))

        // 解线性同余 14 x ≡ 30 (mod 100)
        ok, x0, modBase := solveLinearCongruence(14, 30, 100)
        if ok {
            fmt.Printf("解: x ≡ %d (mod %d)\n", x0, modBase)
        } else {
            fmt.Println("无解")
        }

        // CRT 示例: x ≡ 2 (mod 3), x ≡ 3 (mod 5), x ≡ 2 (mod 7) -> x = 23 mod 105
        res := []int64{2, 3, 2}
        modules := []int64{3, 5, 7}
        x, M, ok := crt(res, modules)
        if ok {
            fmt.Printf("CRT 解: x ≡ %d (mod %d)\n", x, M)
        } else {
            fmt.Println("CRT 失败（可能模不互质）")
        }
    }

3 使用场景

• 应用

密码学：模算术是 RSA 和 Diffie-Hellman 等算法的基础。

哈希：用于哈希函数中，将数据映射到固定大小的值。

数论：求解同余和模方程。

编程：有效处理循环结构，如圆形数组。

4 小结

模算术不直接支持除法。相反，使用模逆。

不同的编程语言可能以不同的方式实现 % （e.g.，作为 C/C++ 中的余数）。

理解模算术对于解决竞争性编程、密码学和算法设计中的问题 至关重要。

• 如何选择与实际注意事项（实战小贴士）

大整数/性能：在加密里，模 n 是很大的（上千位），要使用专门的大整数库（Go 的 math/big、Python 的内建 int 已经支持任意精度，但对于性能敏感场景可能用 C/汇编加速或专用库）。

直接用 % 注意负数：多数语言 % 对负数行为不同（Go、Python 都有定义，但最好做 ((a % n) + n) % n 或封装一个 mod() 保证非负结果）。

模为质数时更方便：若模 p 是素数，所有非零元素都有逆元，很多组合学/模计算可以用费马小定理 a^{p-1} ≡ 1 (mod p) 来加速求逆（a^{-1} ≡ a^{p-2} (mod p)）。

CRT 需模互质：若模不互质，CRT 需要更细致的处理（判断一致性并求通解），示例中省略复杂情况。