每个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。

本文来自企鹅号 - AI讲堂媒体

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏数据结构与算法

P2658 汽车拉力比赛

题目描述 博艾市将要举行一场汽车拉力比赛。 赛场凹凸不平,所以被描述为M*N的网格来表示海拔高度(1≤ M,N ≤500),每个单元格的海拔范围在0到10^9之...

28580
来自专栏窗户

围棋规则的计算机实现

  提到这个名字,很多人会想到前段时间让全世界振奋的围棋人工智能Alphago,想曾经我也了解过一些围棋的AI。我也正想花点时间说说alphago相关的东西,包...

297100
来自专栏菩提树下的杨过

“AS3.0高级动画编程”学习:第二章转向行为(下)

在上一篇里,我们学习了“自主角色”的一些基本行为:寻找(seek)、避开(flee)、到达(arrive)、追捕(pursue)、躲避(evade)、漫游(wa...

290100
来自专栏C语言及其他语言

【每日一题】问题 1247: 筛排处理

关注我们 题目描述 明明想在学校中请一些同学一起做一项问卷调查,为了实验的客观性,他先用计算机生成了N个1到1000之间的随机整数(N<=100),对于其中重...

30180
来自专栏小樱的经验随笔

【经验分享(续篇)】Trachtenberg system(特拉亨伯格速算系统)

之前有篇文章简单地介绍了Trachtenberg系统的乘法计算方法,地址在这里。针对一些特定的数字,Trachtenberg还发展出了更快的计算方法。 先来介绍...

46670
来自专栏数据结构与算法

洛谷P2118 比例简化(暴力)

题目描述 在社交媒体上,经常会看到针对某一个观点同意与否的民意调查以及结果。例如,对某一观点表示支持的有1498 人,反对的有 902人,那么赞同与反对的比例可...

39460
来自专栏温安适的blog

动态规划算法-背包问题

38380
来自专栏菩提树下的杨过

AS3:小游戏“贪吃蛇”的实现

前几天在园子里看到有人用Silverlight做了一个"贪吃蛇",一时兴起也想用AS3.0做一个,虽然这个游戏已经被很多开发者做烂了,但是作为AS的初学者,重新...

36670
来自专栏程序员叨叨叨

6.6 条件操作符(Conditional Operators)

expr1的计算结果为true或者flase,如果是true,则expr2执行运算,否则expr3 被计算。

12830
来自专栏算法channel

回溯树求集合全排列和所有子集

本公众号主要推送关于对算法的思考以及应用的消息。算法思想说来有,分而治之,深度搜索,动态规划,回溯,贪心等,结合这些思想再去思考如今很火的大数据,云计算和机器学...

35990

扫码关注云+社区

领取腾讯云代金券