程序员数论参考
0.皮亚诺公理
整个算术规则都是建立在 5 个基本公理基础之上的，这 5 个基本公理被称为皮亚诺公理。皮亚诺公理定义了自然数所具有的特性，具体如下：
- 0 是自然数；
- 每个自然数都有一个后续自然数；
- 0 不是任何自然数的后续自然数；
- 不同自然数的后续自然数不同；
- 如果集合 S 包含了数字 0，并且包含 S 中的每一个数字的后续自然数，那么集合 S 就包含了所有的自然数。
上述 5 个公理也被称为“数学归纳法的基础”，通常，除了我们想要证明其他算术定理的情况，我们很少直接使用上述公理。但作为算术的基石，这些公理是值得我们去了解的。
1.算术基本定理
算术基本定理是数论中所有概念的核心。又称正整数的唯一分解定理，即：每个大于 1 的自然数均可写为质数的积，而且这些素因子按大小排列后，写法仅有一种方式。例如 \(6936 = 2^3 \times 2 \times 17^2, 1200 = 2^4 \times 2 \times 5^2\)
算术基本定理的内容分两部分组成：
- 分解的存在性；
- 分解的唯一性，即不考虑排列的顺序，正整数分解为素数乘积的方式是唯一的。
2.欧几里得定理
数学中的两个重要定理，欧几里得第一定理和第二定理，内容如下：
- 第一定理：\(p \vert ab => p \vert a or p \vert b\)。该定理的直接结论就是算术基本定理。
- 第二定理：质数的数量是无限的。有很多简单的证明方法。
虽然确实存在无限多的质数，但也应该记住，质数之间存在任意大的差值。换句话说，给定n的前提下，总是可以获得一些列的n个连续复合数。
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) \times [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。
def get_gcd(a, b):
'''
最小公倍数 = 两整数的乘积 / 最大公约数
求最大公约数算法：
有两整数a和b：
① a%b得余数c
② 若c=0，则b即为两数的最大公约数
③ 若c≠0，则a=b，b=c，再回去执行①
'''
m = a
n = b
c = 0
while n != 0:
c = m % n
m = n
n = c
return m, int(a * b / m)
4.整数因式分解
整数因子分解的最常用的算法是 Eratosthenes 筛选法。在分解N时，将质数扫描到 sqrt(N)就足够了。另外，如果我们需要对 1 到 N 之间的所有数字进行因式分解，则可以使用该算法的单次运行来完成此任务 – 对于 1 到 N 之间的每个整数 k ，我们可以保持一对映射——整除 k 的最小质数、最大倍数，(p，a)。k 的剩余质因子与 k/(pa) 的相似。
5.线性同余方程组
形如 \(ax \equiv b (mod n)\) 的方程式（x 是未知数）成为线性同余。当且仅当存在整数 x 使得 \(n \vert (ax - b)\) 成立时，这样的方程组将有一个解，即 \(ax - b = ny\)，y 是整数，换句话说，\(ax + n(-y) = b\)。我们已经从 Bezout 的等式中得知，像这样的线性不定方程将只有在(a, n) 的 gcd （假设该值为 d）整除 b 时才有解。在这种情况下，让 \(b = dd', a = da', n = dn'\)，所以我们有：
- \(da'x + dn'(-y) = dd'\)，其中 \(gcd(a', n') = 1\)
- 带入变量 d
- \[a'x = n'(-y) = d'\]
- 由于 \(gcd(a', n') = 1\)，现在我们可以使用扩展的欧几里得的算法来找到 \(a'x + n'(-y) = 1\) 的解，然后将该解乘以 d’ 得到对于 \(a'x + n'(-y) = d'\) 的解。
注意，如果 \(ax \equiv b (mod n)\) 有一个解，则 \(mod(n / d)\) 有且仅有一个解。如果这个解是用 x0 表示的，那么 mod n 将恰好有 d 个解，由 \(x0 + kn / d\) 给出，其中 k >= 0
参考：
http://developer.51cto.com/art/201710/553504.htm
