17zwd一起做业网站,网站开发账务处理,如何建设网站 知乎,网站目标定位分析这篇文章讨论了数论中每个程序员都应该知道的几个重要概念。本文的内容既不是对数论的入门介绍#xff0c;也不是针对数论中任何特定算法的讨论#xff0c;而只是想要做为数论的一篇参考。如果读者想要获取关于数论的更多细节#xff0c;文中也提供了一些外部的参考文献也不是针对数论中任何特定算法的讨论而只是想要做为数论的一篇参考。如果读者想要获取关于数论的更多细节文中也提供了一些外部的参考文献大多数来自于 Wikipedia 和 Wolfram 。 0、皮亚诺公理 整个算术规则都是建立在 5 个基本公理基础之上的这 5 个基本公理被称为皮亚诺公理。皮亚诺公理定义了自然数所具有的特性具体如下 10是自然数 2每个自然数都有一个后续自然数 30不是任何自然数的后续自然数 4不同自然数的后续自然数不同 5如果集合S包含了数字0并且包含S中每一个数字的后续自然数那么集合S就包含了所有的自然数。 上述第5个公理也被称为“数学归纳法的基础”。 通常除了我们想要证明其他算术定理的情况我们很少直接使用上述公理。但作为算术的基石这些公理是值得我们去了解的。 延伸阅读 https://en.wikipedia.org/wiki/Peano_axioms http://mathworld.wolfram.com/PeanosAxioms.html 1、算术基本定理和除法运算法则 正如这个定理的名称所言算术基本定理是数论中所有概念的核心。算术基本定理含义如下任何一个大于1的整数都可以以某种特定的方式写成质数的乘积的形式这种特定方式取决于乘积中质数的顺序。例如18 2 * 9, 1755 33 *5 * 13. 这个定理在几乎所有的数论运算法则中都扮演着十分重要的角色例如求一个数的质数因子、最大公约数、除数的和等等。想要证明这个定理其实很简单实际上它是欧几里得第一个定理的一个推论下面小节会讨论到。 除法运算法则含义是说给定两个整数abb不等于0那么存在两个整数q和r使得下面的等式成立 a bq r 0 r b 通常我们把q称为商而把r称为余数。如果r 0那么我就说b整除a并且表示为b | a. 延伸阅读 https://en.wikipedia.org/wiki/Fundamental_theorem_of_arithmetic http://mathworld.wolfram.com/FundamentalTheoremofArithmetic.html 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个连续复合数。 延伸阅读Euclids Theorem、Euclids 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。 延伸阅读GCD、Bezouts Identity、Euclids Algorithm、Extended Euclids Algorithm 4、整数因式分解 整数因子分解的最常用的算法是 Eratosthenes 筛选法。在分解N时将质数扫描到 sqrt(N就足够了。另外如果我们需要对 1 到 N 之间的所有数字进行因式分解则可以使用该算法的单次运行来完成此任务 - 对于 1 到 N 之间的每个整数 k 我们可以保持一对映射——整除 k 的最小质数、最大倍数(pa)。k 的剩余质因子与 k/(pa) 的相似。 延伸阅读wikipedia、 interactive animation 5、线性同余方程组 形如ax≡b (mod n)的方程式x是未知数称为线性同余。当且仅当存在整数x使得n | (ax-b)成立时这样的方程组将有一个解即ax -b nyy是整数换句话说ax n-y b。我们已经从Bezout的等式中得知像这样的线性不定方程将只有在an的gcd假设该值为d整除b时才有解。在这种情况下让b dda dan dn所以我们有 dax dn - y dd其中gcdan 1 带入变量d ax n - y d。 由于gcdan 1现在我们可以使用扩展的欧几里德的算法来找到ax n - y 1的解然后将该解乘以d得到对于ax n - y d的解。 注意如果ax≡bmod n有一个解则modn / d有且仅有一个解。如果这个解是用x0表示的那么mod n将恰好有d个解由x0 kn/d给出其中0 kd。在关于二次方程的教程中详细讨论了这一点。 延伸阅读Linear Congruence Theorem、Solving Linear Congruences 6、中国剩余定理 典型的问题形式是“寻找一个数除以2余1除以3余2除以7余5”其余各项可以被推广为一元线性同余方程组之后可以使用中国剩余定理来解决。举个例子下面的问题可以被表示为三个线性同余式“x ≡ 1 (mod 2), x ≡ 2 mod(3), x ≡ 5 mod (7)” 也就是一元线性同余式方程组 x ≡ a1 (mod n1) x ≡ a2 (mod n2) x ≡ a3 (mod n3) .... x ≡ ak (mod nk) 假设整数ni,nj两两互质则对任意的nn1n2...nk方程组有解 对于任意的i当0 di ni令cin/ni令di为同余式cix1(mod ni)的解这个解法可以在利用扩展的欧几里德算法。上面的线性方程组的通解可以给出为 c a1c1d1 a2c2d2 ... akckdk 中国剩余定理的直接推论如下假设 n p1a1 * p2a2 * .... * pkak 为 n 的素因子分解。 那么对于任何整数 a 和 b我们对于每个 i 都有 a b (mod n) iff a b (mod piai ) 。 讨论一下 Ni 的不一定都是两两互质的中国剩余定理的推广如下 - 线性同余系统 x≡a1mod n1 x≡a2mod n2 x≡a3mod n3 .... x≡akmod nk 有解当对于每个 i ! j 都有 iff gcd(ni,nj) 除 (ai-aj) 且存在唯一解 mod n其中 n 是 n1n2 ... nk 的最小公倍数 进一步阅读中国剩余定理求解线性同余小程序 7、二次方一致性 给定 q 和 n如果等式 x2≡qmod n 具有解则 q 称为二次残差的模 n。如果该方程不具有解则q被称为“二次非残差”。例如x2≡9mod 15具有解 x 12因此 9 是模 15 的二次余数。另一方面等式 x2≡11mod 15没有解因此 11 是二次非残差为了简单起见如果一个正方形可以取一些正整数 n 的形式nk q则整数 q 是模 n 的二次余数。 发现具有质数模的二次一致性是否具有一个解是有些容易的x2≡amod p只有在p-1/ 2 1mod p时才具有解。 在这种情况下可以使用 Shank-Tonelli 算法来获得解决方案。 延伸阅读: 二次残差、二次互反性、模拟、Shank-Tonelli算法、E4手册 8、欧拉 Phi 函数、除数函数、约数和、Mobius 函数 欧拉的 Phi 函数 又称为常数函数由φ表示是自然数的函数给出与相应的自然数互质的正整数的数目。因此φ(8) 4 φ(9) 6 等。 该函数的以下属性值得注意 a) 如果 p 是素数则 φ(pk) (p-1)pk-1 b) φ 函数是乘法的即如果 if (a,b) 1 则 φ(ab) φ(a)φ(b)。 c) φ(n) 的值可以通过欧拉公式获得令 n p1a1 * p2a2 * .... * pkak 是 n 的素因子分解。则 φ(n) n * (1- 1/p1)) * (1- 1/p2)) * ... * (1- 1/pk)) d) 以编程方式如果我们欲求 1 到 n 的 φ 那么我们可以非常好地使用筛选算法连同 φ 的乘法性质。中心思想是如果 n 是素数则 φ(n) n-1。否则如果 n 是素数的幂例如 n pk则 φ(n) (p-1)pk-1。否则对于某个素数p令 npk*q 。使用乘法属性 我们有 φ(n) φ(pk)φ(q) φ(n) 的两个重要属性 i. aφ(n) ≡ 1 (mod n) 每当 (a,n) 1。 具体来说 对于素数p如果 p 不能整除 a则 ap-1 ≡ 1 (mod p)。 这种特化也被称为费马小定理。 ii. 令 d1, d2, ...dk 为 n 的所有除数包括 n。则 φ(d1) φ(d2) ... φ(dk) n 例如18的除数是1、2、3、6、9 和 18。观察到 φ(1) φ(2) φ(3) φ(6) φ(9) φ(18) 1 1 2 2 6 6 18 该除数函数表示为 d(n)给出了一个自然数的除数的数目。例如d(18) 6。类似地除数函数之和表示为 σ(n)给出了 n 的除数的和。 因此σ(18) 1236918 39。关于这两个函数以下属性毫无价值 a) 如果 p 是素数则 d(p) 2。另外 d(pk) k1 并且 σ(p) p1 b) 如果 n 是两个不同的素数的乘积假使 n pq 则 σ(n) n1(pq)。另外观察到这种情况φ(n) n1-(pq)。 c) 一般来说令 n p1a1 * p2a2 * .... * pkak 。则 d(n) (a11) * (a21) * ... (ak 1)并且 σ(n) 由以下乘积给出 σ(n) ( (p1(a11) - 1) / (p1-1) ) * ( (p2(a21) - 1) / (p2-1) ) * ... * ( (pk(ak1) - 1) / (pk-1) ) 如果 σ(n) 2n则 n 被称为“完全数”。换句话说 完全数的真因子即除了自身以外的除数的和恰好等于它本身。 mobius函数µ(n) 在所有正整数中定义如下 在 n 是非平方数即 n 是不能被任意整数平方得到并且 n 有偶数个不同的素数因子则 µ(n) 1 在 n 是非平方数即 n 是不能被任意整数平方得到并且 n 具有奇数个不同素数因子则µ(n) -1 在 n 是平方数即 n 是某个整数的平方则 µ(n) 0 Mobius 函数是乘法分配性的即 a 和 b 互为质数则 µ(ab) µ(a)*µ(b). 计算欧拉方程函数的一个有用公式可以用 mobius 函数给出令 d1d2... dk 为 n 的所有除数。然后 φ(n) (d1 * mu (n/d1) ) (d2 * µ(n/d2) ) .... (dk * µ(n/dk) ) 这也可以写成 φ(n) (µ(d1) * (n/d1) ) (µ(d2) * (n/d2) ) .... (µ(dk) * (n/dk) ) 使用筛选法计算 phi[n] 的 Java 实现如下 //read/get n int phi[] new int[n1];
for(int i2; i n; i) phi[i] i; //phi[1] is 0 for(int i2; i n; i)
if( phi[i] i )
for(int ji; j n; j i )
phi[j] (phi[j]/i)*(i-1); 阶乘 阶乘是非常重要的。N 的阶乘定义如下N (N)*(N-1)*(N-2)*(N-3)...1。在计算 nPr nCr 时需要使用阶乘。他们像这里描述的那样很快变得非常大所以他们需要非常仔细的处理大数、大整数表示等。 延伸阅读欧拉的 Totient 函数、除数函数、除数和总和、Mobius函数 到此我们完成了对基本数理论概念的讨论。对于那些对数理论感兴趣的人这里有一些值得一读的书—— An introduction to the theory of numbers: by Niven, Zukerman and Montgomery 数论导论 Elementary Number Theory : by David Burton 数论基础 整数序列 流行的整数序列有很多。它们中的许多都基于递归关系。主要的定理被广泛用于了解其复杂性边界与循环的关系。很多流行的整数序列例如费布那切数列鲁卡斯数字, 斯特恩双原子数字, 懒卡特数字, 帕多万数字 还有多边形数字诸如 五角形数字, 六角形数字。 对数论的介绍哈迪和赖特 初等数论: 琼斯和琼斯 数学诱导 - 一种技术教程经常用于离散空间的证明。 具有数学归纳原理的问题和解决方案的教程。 来自开源中国社区 链接https://www.oschina.net/translate/tutorial-number-theory 原文https://www.codechef.com/wiki/tutorial-number-theory/
