专栏首页人工智能每个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。

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

我来说两句

0 条评论
登录 后参与评论

相关文章

  • Python数据分析系列(1)——品味葡萄酒

    作者:王大伟 Python爱好者社区唯一小编 博客:https://ask.hellobi.com/blog/wangdawei ? 前言 数据分析学习了挺久,...

    企鹅号小编
  • 编程语言之间的百舸争流

    编程语言排行榜 TIOBE编程语言社区发布了2017年11月排行榜,Java、C、C ++三门编程语言依然占据前三。11月前5排名中,最值得注意的是:Pytho...

    企鹅号小编
  • 腾讯这一波,又会带火哪些域名?

    目前,只需要将微信客户端升级到最新版本,就能体验微信的这个新功能了。相信不少人也已经被下面这个图给刷屏了: ? 许多人都反映,“跳一跳”实在是太好玩了,一不小心...

    企鹅号小编
  • 有没有无痛无害的人体成像方法?OCT(光学相干断层扫描)了解一下

    关于之前推送的胸片和CT有很多的小伙伴关心射线对人体的伤害的问题,在医学检查射线的强度和剂量已经有严格的标准,偶尔进行一次CT扫描是没有问题的,那么有没有一种完...

    用户1150922
  • 如何找到cache-control header是从后台何处设置的

    在请求Fiori launchpad时,观察FuoriLaunchpad.html的请求:

    Jerry Wang
  • Qt官方示例-QML扩展对象

    ❝该示例展示如何使用qmlRegisterExtendedType()将扩展对象(LineEditExtension)提供给QLineEdit,而无需对其进行修...

    Qt君
  • 如果你每次面试前都要去背一篇Spring中Bean的生命周期,请看完这篇文章

    当你准备去复习Spring中Bean的生命周期的时候,这个时候你开始上网找资料,很大概率会看到下面这张图:

    程序员DMZ
  • cvxopt 示例简单讲解

    Cvxopt 是基于 Python 语言的用于解决凸优化问题的免费包,可以用于求解纳什均衡问题的最优策略,好用但是不容易理解,

    杨熹
  • Vue学习-设计模式探索

    我们假定,存在一个"信号中心",某个任务执行完成,就向信号中心"发布"(publish)一个信号,其他任务可以向信号中心"订阅"(subscribe)这个信号,...

    Caleb
  • SpringMVC(二)

    bgZyy

扫码关注云+社区

领取腾讯云代金券