《算法竞赛中的初等数论》（二）正文 0x20同余（ACM _ OI _ MO）（十五万字符数论书） (1)1

《算法竞赛中的初等数论》是一本专为ACM、OI、MO竞赛选手和对算法感兴趣的读者编写的书籍，涵盖了丰富的数论基础知识。本文主要关注的是整除和同余的概念，这对于解决算法竞赛中的数学问题至关重要。 整除是数论的基础，指的是一个整数能够被另一个整数整除而没有余数。比如，10可以被2整除，因为10除以2的结果是5，没有余数。在计算机编程中，整除通常用"/"表示，取余则用"%"表示。带余除法是整除的一种形式，它包括商和余数两个概念，例如，17除以5得到商3和余数2，记作17 = 5 × 3 + 2。 模运算（取余运算）是整数除法后得到的余数，如17 % 5等于2。模运算具有几个重要的性质，包括结合律（(a % m) % n == a % (m * n)）、交换律（a % b == b % a，前提是a和b都与模数互质）和分配律（a % m * b % m == (a * b) % m）。这些性质在算法中经常用于简化计算。 接下来，文章介绍了同余的概念，即两个整数如果除以同一个正整数的余数相等，就说它们是同余的，记作a ≡ b (mod m)。同余有若干重要性质，如若a ≡ b (mod m)且c ≡ d (mod m)，则a ± c ≡ b ± d (mod m)和ac ≡ bd (mod m)。此外，费马小定理指出，如果a和p是互质的整数，那么a^(p-1) ≡ 1 (mod p)。欧拉定理是费马小定理的一个推广，它表明，如果a和φ(m)是互质的，那么a^φ(m) ≡ 1 (mod m)，其中φ(m)是欧拉函数，表示小于等于m且与m互质的正整数个数。 扩展欧几里德算法是求解最大公约数（GCD）和贝祖定理（Bézout's identity）的工具，它不仅可以找到两个整数的最大公约数，还可以找到它们的线性组合，使得这个组合等于它们的GCD。这个算法在解决模线性方程组中非常有用。 乘法逆元是模运算的一个重要概念，它是指一个数a在模m意义下的逆元素，使得aa^-1 ≡ 1 (mod m)。乘法逆元在解决模算术问题时起到关键作用，可以通过扩展欧几里德算法或者线性递推方法求得。 线性同余方程组，特别是中国剩余定理，是解决多个模同余方程的问题。中国剩余定理提供了解决这类问题的通用框架，而拓展中国剩余定理则解决了更一般的情况。 在算法竞赛中，这些数论概念常用于解决涉及公约数、最大公约数、最小公倍数、同余方程等问题。例如，公约数之和题目要求计算一组数的公约数总和，这可以通过理解整除和同余的性质来高效解决。 《算法竞赛中的初等数论》深入浅出地讲解了整除、同余、模运算和相关定理，是算法竞赛和数论学习者的宝贵资源。通过理解和掌握这些知识，读者可以更好地应对算法竞赛中的数学挑战。