每个AI程序员都应该知道的基础数论

-欢迎

加入AI技术专家社群>>

这篇文章讨论了数论中每个程序员都应该知道的几个重要概念。本文的内容既不是对数论的入门介绍，也不是针对数论中任何特定算法的讨论，而只是想要做为数论的一篇参考。如果读者想要获取关于数论的更多细节，文中也提供了一些外部的参考文献（大多数来自于 Wikipedia 和 Wolfram ）。

0、皮亚诺公理

整个算术规则都是建立在 5 个基本公理基础之上的，这 5 个基本公理被称为皮亚诺公理。皮亚诺公理定义了自然数所具有的特性，具体如下：

（1）0是自然数；

（2）每个自然数都有一个后续自然数；

（3）0不是任何自然数的后续自然数；

（4）不同自然数的后续自然数不同；

（5）如果集合S包含了数字0，并且包含S中每一个数字的后续自然数，那么集合S就包含了所有的自然数。

上述第5个公理也被称为“数学归纳法的基础”。

通常，除了我们想要证明其他算术定理的情况，我们很少直接使用上述公理。但作为算术的基石，这些公理是值得我们去了解的。

延伸阅读：

https://en.wikipedia.org/wiki/Peano_axioms

1、算术基本定理和除法运算法则

正如这个定理的名称所言，算术基本定理是数论中所有概念的核心。算术基本定理含义如下：任何一个大于1的整数都可以以某种特定的方式写成质数的乘积的形式（这种特定方式取决于乘积中质数的顺序）。例如，18 = 2 * 9, 1755 = 33 *5 * 13. 这个定理在几乎所有的数论运算法则中都扮演着十分重要的角色，例如求一个数的质数因子、最大公约数、除数的和等等。想要证明这个定理其实很简单，实际上它是欧几里得第一个定理的一个推论（下面小节会讨论到）。

除法运算法则含义是说：给定两个整数a，b（b不等于0），那么存在两个整数q和r使得下面的等式成立：

a = bq + r， 0

通常我们把q称为商，而把r称为余数。如果r = 0，那么我就说b整除a，并且表示为：b | a.

延伸阅读：

https://en.wikipedia.org/wiki/Fundamental_theorem_of_arithmetic

https://en.wikibooks.org/wiki/Number_Theory/Elementary_Divisibility

https://en.wikipedia.org/wiki/Division_algorithm

2、欧几里得定理

数学中两个重要定理，被称为“欧几里德的第一定理（或欧几里德的引理）”和“欧几里德的第二定理（通常简称为”欧几里德定理“），内容如下：

第一定理：p|ab => p|a or p|b。该定理的直接结论就是算术基本定理。

第二定理：质数的数量是无限的。有很多简单的证明方法。

虽然确实存在无限多的质数，但也应该记住，质数之间存在任意大的差值。换句话说，给定n的前提下，总是可以获得一些列的n个连续复合数。

延伸阅读：Euclid's Theorem、Euclid's Lemma、walfram

3、最大公约数、最小公倍数和贝祖定理

欧几里得算法是求两个数的最大公约数最常用的算法，而且也是一个很高效的算法，因为使用欧几里得算法求解两个数的最大公约数的算法步骤最多不会超过这两个数中较小的那个数的5倍。最大公约数通常使用圆括号表示—— (a,b) 表示a和b的最大公约数。类似地，最小公倍数通常使用方括号表示—— [a,b] 表示a和b的最小公倍数。

如果 (a,b) = 1，即 [a,b] = ab，此时我们称a和b互质。

如果 (a,b) = d，那么 (a/d,b/d) = 1。

最大公约数和最小公倍数之间的关系可以由一个非常简单的等式来表示：(a,b) * [a,b] = ab. 该等式为我们提供了一种快速计算两个数的最小公倍数的方法。

贝祖定理是说，如果 d = （a,b） 那么一定存在整数 x 和整数 y 满足 ax + by = d. （当然，如果存在的话，那么线性双变量方程的理论保证了无穷多解的存在性）。同样值得注意的是，k = d 是满足 ax + by = k 有一个关于 x 和 y 的解的最小正整数。

指定 a 和 b，我们可以通过递归或迭代的方式实现扩展的欧几里得算法来求解满足等式 ax + by = d 的 x 和 y。