主要的

Article

May 24, 2022

质数是大于 1 的自然数,它不是两个较小的自然数的乘积。换句话说,质数是恰好有两个除数的数,1 和它本身。大于 1 的非质数的自然数称为合数。例如,5 是素数,因为只有将它写成乘积的方式,1 × 5 或 5 × 1,其因数是 5 本身。但是,4 是合数,因为它是两个数 (2 × 2) 的乘积其中小于 4。根据算术基本定理,素数是数论的核心:每个大于 1 的自然数要么是素数,要么只能通过置换分解为素数。素数的性质称为素数。一种测试数 n {\displaystyle n} 素数的简单方法,称为试除算法,检查 n {\displaystyle n} 是否是 2 和 n {\displaystyle {\sqrt {n} 之间的任何整数的倍数}} 或不。其他一些算法包括 Miller-Rabin 测试,它速度快但给出错误结果的概率很小,以及 AKS 素性测试,它总是在多项式时间内给出正确的解决方案,但速度太慢而无法实际应用。还有一些特殊形式的数的快速算法,例如梅森素数。截至 2020 年 12 月,已知的最大素数有 24,862,048 位,于 2018 年 12 月被发现。 欧几里得在公元前 300 年左右证明了素数有无穷多个。几乎没有简单的公式来区分质数和合数。但是,自然数集合中质数在大范围值上的分布可以通过统计建模。这个方向的第一个结果是质数定理,在 19 世纪末得到证明,它指出任何数为质数的概率与其位数成反比,即与它的对数成反比。一些涉及素数的历史问题仍未解决。其中包括哥德巴赫猜想,它指出每个大于 2 的偶数都可以表示为两个素数之和,以及孪生素数猜想,它指出有无穷多对素数之间只有一个偶数。这些问题促成了数论的许多分支的发展,这些分支侧重于数的代数和解析方面。质数在某些信息技术领域也有应用,例如公钥密码学,它依赖于大整数因式分解的复杂性。在抽象代数中,还有许多其他具有与素数相似的特性和性质的对象,包括素元素和素理想。在抽象代数中,还有许多其他具有与素数相似的特性和性质的对象,包括素元素和素理想。在抽象代数中,还有许多其他具有与素数相似的特性和性质的对象,包括素元素和素理想。

定义和示例

如果一个自然数 (1, 2, 3, 4, 5, 6,...) 大于 1 并且不能表示为两个较小自然数的乘积,则称其为素数。大于 1 的非质数的数称为合数。换句话说,如果 n {\displaystyle n} 个对象不能被平均分成多个对象的多个子组,或者 n {\displaystyle n} 点不能排列成一个矩形,则 n {\displaystyle n} 是质数长和宽不超过一个点。例如,在数字 1 到 6 中,数字 2、3 和 5 是质数,因为没有其他数字可以被它们整除(余数为零)。 1 不是素数,因为它已被排除在定义之外。 4 2 × 2 和 6 2 × 3 都是合数。自然数 n {\displaystyle n} 的约数是能被 n {\displaystyle n} 整除的自然数。每个自然数至少有两个约数,1 和它本身。如果它有另一个除数,它就不能是素数。从这个想法衍生出素数的另一个定义:那些恰好有两个正除数的素数,1 和它本身。还有另一个表达式: n {\displaystyle n} 是素数,如果它大于 1 并且没有任何数字 2 , 3 , … , n − 1 {\displaystyle 2,3 ,\dots ,n-1} 是可整除的通过它。前25个素数(所有小于100的素数)是:2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67 , 71, 73, 79, 83, 89, 97(OEIS表中的A000040系列)。没有大于2的偶数n {\displaystyle n} 是素数,因为偶数是不规则的。周期可以表示为2 × n / 2 {\displaystyle 2\times n/2} .因此,除2以外的所有素数都是奇数,称为奇素数。类似地,当以十进制书写时,所有大于 5 的素数都以 1、3、7 或 9 结尾。以另一位结尾的数是合数:以 0、2、4、6 或 8 结尾的数是偶数,结尾的数是在 0 或 5 中可以被 5 整除。素数集用 P {\displaystyle \mathbf {P} } 或 P {\displaystyle \mathbb {P} } 表示。

历史

Rhind Papyrus(约公元前 1550 年)包含各种形式的质数和合数的埃及分数展开式。然而,现存最早的质数具体研究来自古希腊数学。 Euclid's Basis (c. 300 BC) 包含无限数量素数存在的证明和算术基本定理,并展示了如何从梅森素数生成一个完美数。希腊的另一项发明是埃拉托色尼筛,它仍然用于制作素数列表。大约在公元 1000 年,伊斯兰数学家 Ibn al-Haytham (Alhazen) 发现了威尔逊定理,确定素数。是数字 n {\ displaystyle n} 是可整除的 ( n − 1 ) !+ 1 {\displaystyle (n-1)!+1} .他还推测,在欧几里德的构造中,所有甚至完全数都可以从梅森数导出,但未能证明。另一位伊斯兰数学家 Ibn al-Banna' al-Marrakushi 发现,通过只测试与测试的最大数的平方根一样大的除数,可以加速 Eratosthenes 的筛选。斐波那契随后将这些来自伊斯兰数学的新思想带到了欧洲。他的 Liber Abaci (1202) 是第一本描述试除算法的书,该算法仅通过测试与要测试的数字的平方根一样大的除数来测试素性。1640 年,皮埃尔·德·费马 (Pierre de Fermat) 陈述了费马小定理(后来证明莱布尼茨和欧拉)。费马还研究并测试了费马 2 2 n + 1 {\displaystyle 2^{2^{n}}+1} 的素性,而 Marin Mersenne 研究了梅森素数,形式为 2 p − 1 {\displaystyle 2^ {p}-1} 其中 p {\displaystyle p} 也是素数。在 1742 年给欧拉的信中,克里斯蒂安·哥德巴赫陈述了哥德巴赫猜想,即每个偶数都是两个质数之和。Euler 证明了 Alhazen 的猜想(后来称为 Euclid-Euler 定理),即每个偶完全数都可以从梅森素数产生。他还介绍了数学分析在该领域应用的方法,以证明无限数量的素数的存在和素数的倒数之和的散度 1 2 + 1 3 + 1 5 + 1 7 + 1 11 +⋯{\ displaystyle {\tfrac {1}{2}}+{\tfrac {1}{3}}+{\tfrac {1}{5}}+{\tfrac {1} {7}}+{\tfrac{1}{11}}+\cdots } . 19世纪初,勒让德和高斯推测,随着 x {\displaystyle x} 趋近无穷大,小于或等于 x {\displaystyle x} 的素数的数量渐近于 x / log ⁡ x {\ displaystyle x/\log x} 其中 log ⁡ x {\displaystyle \log x} 是 x {\displaystyle x} 的自然对数。伯恩哈德·黎曼 (Bernhard Riemann) 在 1859 年关于 zeta 函数的工作中的想法为证明该猜想奠定了基础。虽然一个相关的猜想,黎曼猜想,仍然没有答案,黎曼的大纲由 Hadamard 和 de la Vallée Poussin 于 1896 年完成,其结果现在被称为素数定理。 19 世纪的另一个重要成就是关于加法方程的狄利克雷定理,该定理指出给定的等差数列包含无限个素数。许多数学家已经研究了用整数检查素性的算法。数字大于那些可以应用试用分割算法。限制特定数字形式的算法包括 Fermat 数的 Pépin 检验 (1877)、Proth 定理(大约 1878 年)、Lucas-Lehmer 检验(1856 年)及其一般形式 Lucas 检验。自 1951 年以来,所有已知的最大质数是通过计算机算法找到的。通过 Great Internet Mersenne Prime Search 项目和许多其他分布式计算项目,寻找比这更大的质数的努力在数学之外获得了关注。质数在纯数学之外几乎没有应用的概念在 1970 年代被摒弃,当时基于质数发明了公钥密码学和 RSA 加密。可以用非常大的数字执行的其他算法,这些数字不是任何特殊形式。质数的数学理论在现代也继续发展,格林-陶定理 (2004) 指出存在任意长度的等差数列只包含质数,以及 Yitang Zhang 在 2013 年的证明,即存在无限多个有限大小的素数距离。

计算数字1的素数

大多数古希腊数学家不认为 1 是一个数字,因此他们不能考虑它的质数。当时的一些数学家也认为质数是由奇数的除法得到的,所以他们不认为数字2是质数。然而,欧几里得和大多数古希腊数学家都认为 2 是一个质数。伊斯兰数学家也追随希腊人,不承认 1 是一个数字。在中世纪和文艺复兴时期,数学家开始接受 1 作为一个数,其中一些人认为 1 是第一个质数。 18 世纪中叶,克里斯蒂安·哥德巴赫在给莱昂哈德·欧拉的信中承认数字 1 是质数,但欧拉不同意。许多 19 世纪的数学家仍然认为 1 是素数,包含数字 1 的素数列表一直持续到 1956 年。如果将质数定义更改为将 1 识别为质数,那么与它相关的许多定理将不得不复杂地重新表述。例如,算术的基本定理将被解析重写为大于 1 的素数,因为每个数都有无数种分析方法,其中数 1 出现的次数不规则。类似地,Eratosthenes 的筛子也不会正常工作,因为它随后会丢弃所有 1 的倍数(即所有其他数字)并仅输出数字 1。素数的某些性质对于数字 1 也不成立:例如,非欧拉函数的公式或从素数到 1 的因数之和。 到 20 世纪初,数学家开始认为数字 1 不应该在素数列表中,而应该是在一个特殊的概念:“单位”在环论中。

基本属性

唯一的分析

写出质数的乘积称为该数的质因数分解。例如:34866 2 ⋅ 3 ⋅ 3 ⋅ 13 ⋅ 149 2 ⋅ 3 2 ⋅ 13 ⋅ 149。{\displaystyle {\begin{aligned}34866&2\cdot 3\cdot 3\cdot 13\cdot 149\\&2\cdot 3^{2}\cdot 13\cdot 149.\end{aligned}}} 乘积中的因数称为质因数。一个质因数可以出现多次,然后可以使用幂将许多相同的因数组合成一个。在上面的例子中,数字 3 出现了两次,3 2 {\displaystyle 3^{2}} 是 3 的 2 的平方或幂。素数在数论和数学中的本质重要性。一般从基本定理得到算术。该定理指出,任何大于 1 的整数都可以写为一个或多个素数的乘积。此外,该产品是独一无二的,因为很容易在相同数字的两个素数分析中看到,质因数总是出现相同的次数,即使它们的顺序可能不同。因此,尽管通过整数解析算法找到解析数字的方法有不同的方法,但它们都必须给出相同的结果。因此素数也被称为自然数的“积木”。素数分析唯一性的一些证明是基于欧几里德引理的:如果 p {\displaystyle p} 是素数并且 p {\displaystyle p} 可以被 a {\displaystyle a} 和 b {\displaystyle b} 是整数的积 a {\displaystyle ab} 整除,那么 p {\displaystyle p } 也可以被 a {\displaystyle a} 或 b {\displaystyle b}(或两者)整除。相反,如果一个数 p {\displaystyle p} 具有这样的性质,即当它可以被乘积整除时,它也可以被乘积中的至少一个因子整除,那么 p {\displaystyle p} 必须是素数。

无限多个素数的存在

有无穷多个素数。换句话说,素数序列 2, 3, 5, 7, 11, 13,... 永远不会结束。上述命题也因古希腊数学家欧几里得(Euclid)而被称为欧几里得定理,因为他是第一个证明这一命题的人。存在无穷多个素数的其他一些证明包括欧拉的解析证明、基于费马数的哥德巴赫证明、弗斯滕伯格的拓扑证明或简单的证明。库默尔的证明。欧几里德的证明表明任何有限的素数集都是不完整的.事实上,考虑一个有限的素数集 p 1 , p 2 , … ,p n {\displaystyle p_{1},p_{2},\ldots ,p_{n}} .当将这些数字相乘并加 1 时,我们得到 N 1 + p 1 ⋅ p 2 ⋯ p n 。 {\displaystyle N1+p_{1}\cdot p_{2}\cdots p_{n}。根据算术基本定理,N {\displaystyle N} 有一个素数分析 N p 1 ′ ⋅ p 2 ′ ⋯ pm ′ {\displaystyle Np'_{1}\cdot p'_{2} \cdots p '_{m}} 具有一个或多个素因数。 N {\displaystyle N} 可以被上述任何乘积整除,但被给定集合中的任何素数除的余数为 1,所以在那个集合中没有 N {\displaystyle N} 的质因数。由于没有所有素数的有限集合,所以一定有无限多个素数。将最小素数的乘积加 1 所产生的数称为欧几里得数。前五个欧几里得数是素数,但第六个,1 + ( 2 ⋅ 3 ⋅ 5 ⋅ 7 ⋅ 11 ⋅ 13 ) 30031 59 ⋅ 509 , {\displaystyle 1+{\big (}2\cdot 3 \cdot 5\ cdot 7\cdot 11\cdot 13{\big )}3003159\cdot 509,} 是复合的。由于没有所有素数的有限集合,所以一定有无限多个素数。将最小素数的乘积加 1 所产生的数称为欧几里得数。前五个欧几里得数是素数,但第六个,1 + ( 2 ⋅ 3 ⋅ 5 ⋅ 7 ⋅ 11 ⋅ 13 ) 30031 59 ⋅ 509 , {\displaystyle 1+{\big (}2\cdot 3 \cdot 5\ cdot 7\cdot 11\cdot 13{\big )}3003159\cdot 509,} 是复合的。由于没有所有素数的有限集合,所以一定有无限多个素数。将最小素数的乘积加 1 所产生的数称为欧几里得数。前五个欧几里得数是素数,但第六个,1 + ( 2 ⋅ 3 ⋅ 5 ⋅ 7 ⋅ 11 ⋅ 13 ) 30031 59 ⋅ 509 , {\displaystyle 1+{\big (}2\cdot 3 \cdot 5\ cdot 7\cdot 11\cdot 13{\big )}3003159\cdot 509,} 是复合的。将最小素数的乘积加 1 所产生的数称为欧几里得数。前五个欧几里得数是素数,但第六个,1 + ( 2 ⋅ 3 ⋅ 5 ⋅ 7 ⋅ 11 ⋅ 13 ) 30031 59 ⋅ 509 , {\displaystyle 1+{\big (}2\cdot 3 \cdot 5\ cdot 7\cdot 11\cdot 13{\big )}3003159\cdot 509,} 是复合的。将最小素数的乘积加 1 所产生的数称为欧几里得数。前五个欧几里得数是素数,但第六个,1 + ( 2 ⋅ 3 ⋅ 5 ⋅ 7 ⋅ 11 ⋅ 13 ) 30031 59 ⋅ 509 , {\displaystyle 1+{\big (}2\cdot 3 \cdot 5\ cdot 7\cdot 11\cdot 13{\big )}3003159\cdot 509,} 是复合的。1 + ( 2 ⋅ 3 ⋅ 5 ⋅ 7 ⋅ 11 ⋅ 13 ) 30031 59 ⋅ 509 , {\displaystyle 1+{\big (}2\cdot 3\cdot 5\cdot 7\cdot 11\cdot 13{\big ) }3003159\cdot 509,} là hợp số。1 + ( 2 ⋅ 3 ⋅ 5 ⋅ 7 ⋅ 11 ⋅ 13 ) 30031 59 ⋅ 509 , {\displaystyle 1+{\big (}2\cdot 3\cdot 5\cdot 7\cdot 11\cdot 13{\big ) }3003159\cdot 509,} là hợp số。

素数公式

没有已知的有效素数公式。例如,没有非常数多项式,包括多变量多项式,仅适用于素数。但是,有一些表达式可以产生素数,但性能相当低。这样的公式基于威尔逊定理,可以多次给出值 2,其他素值恰好一次。由 9 个变量和一个参数组成的丢番图方程组也存在具有以下性质:当且仅当所得方程组在自然数集上有解,该参数才是素数。这个性质可以用来推导出一个公式,它的所有正值都是素数。另外两个素数公式来自米尔斯定理,一个来自赖特定理,假设有一个实常数 A > 1 {\displaystyle A>1} 和 μ {\displaystyle \mu } 使得 ⌊ A 3 n ⌋ 和 2 ⋯ 2 2 μ {\displaystyle \left\lfloor A^{3^{n}}\right\rfloor{\text{ and }}\left\lfloor 2^{\cdots ^{2^{2^{\mu }}}}\right\rfloor } 是所有自然数的素数 n {\displaystyle n}第一个公式和第二个中的任何权力。这里 ⌊ ⋅ ⌋ {\displaystyle \lfloor {}\cdot {}\rfloor } 是楼层函数,小于或等于被考虑数的最大数。然而,这些公式没有用,因为需要首先生成素数来计算 A {\displaystyle A} 或 μ {\displaystyle \mu } 。这里 ⌊ ⋅ ⌋ {\displaystyle \lfloor {}\cdot {}\rfloor } 是楼层函数,小于或等于被考虑数的最大数。然而,这些公式没有用,因为需要首先生成素数来计算 A {\displaystyle A} 或 μ {\displaystyle \mu } 。这里 ⌊ ⋅ ⌋ {\displaystyle \lfloor {}\cdot {}\rfloor } 是楼层函数,小于或等于被考虑数的最大数。然而,这些公式没有用,因为需要首先生成素数来计算 A {\displaystyle A} 或 μ {\displaystyle \mu } 。

未解决的问题

已经提出了许多关于素数的理论,但其中大部分理论几十年来都没有得到证实:朗道 1912 年的所有四个问题仍未解决。其中之一是哥德巴赫猜想,即每一个大于 2 的偶数 n {\displaystyle n} 都可以写成两个素数之和。截至 2014 年,该猜想已被证实适用于大至 n 4 ⋅ 10 18 {\displaystyle n4\cdot 10^{18}} 的数字。已经证明了几个类似的猜想,例如维诺格拉多夫定理,即一个足够大的奇数整数可以写成三个素数的和。根据陈氏定理,一个足够大的偶数可以表示为一个素数和一个半素数(两个素数的乘积)之和。此外,大于 10 的偶数可以写成 6 个素数之和。处理此类问题的数论分支称为数加法。另一类问题与素数间距有关,即两个连续素数之间的差。通过注意到序列 n ! + 2 , n ! + 3 , ... , n ! + n {\displaystyle n!+2,n!+3,\dots ,n!+n} 包含 n − 1 {\displaystyle n-1} 复合,其中 n {\displaystyle n} 是自然数。然而,这个巨大的质数差距开始出现的时间早于这个论证给出的。例如,长度为 8 的第一个质数距离在数字 89 和 97 之间,远小于 8 ! 40320 {\displaystyle 8!40320} .假设有无限多对孪生素数,即差为 2 的素数对;这就是孪生素数假设。 Polignac 猜想更一般地说,对于任何正整数 k {\displaystyle k},存在无穷多对相差 2 k {\displaystyle 2k} 的连续假素数对。 Andrica 猜想、Brocard 猜想、Legendre 猜想和 Oppermann 猜想都假设从 1 到 n {\displaystyle n} 的素数之间的最大距离应该近似为 n {\displaystyle {\sqrt {n} }} ,结果是据说是从黎曼猜想导出的,而克拉梅猜想将最大距离设置为 O ( ( log ⁡ n ) 2 ) {\displaystyle O((\log n)^{2 })} 。素数距离可以推广到 k {\displaystyle k} 素数的集合,一个由两个以上素数之间的距离组成的集合。它们的无穷大和密度是第一个 Hardy-Littlewood 猜想中的关键问题,它可以从启发式算法推导出来,质数序列与具有密度的随机数序列具有相同的性质,由质数定理给出。

微积分中的性质

解析数论通过连续函数、极限、无穷级数以及与无穷大和无穷小数相关的概念来研究数论。 Leonhard Euler 是第一个发起这项研究的人,他的第一个重要成就是解决了巴塞尔问题。该问题要求找到无穷和的值 1 + 1 4 + 1 9 + 1 16 + … {\displaystyle 1+{\tfrac {1}{4}}+{\tfrac {1}{9}}+ {\tfrac {1}{16}}+\dots } 现在被认为是黎曼 zeta 函数的值 ζ ( 2 ) {\displaystyle \zeta (2)} 。该函数与素数和黎曼猜想密切相关,黎曼猜想是数学中最重要的未解决问题之一。欧拉证明了 ζ ( 2 ) π 2 / 6 {\displaystyle \zeta (2)\pi ^{2}/6} 。该数的倒数 6 / π 2 {\displaystyle 6/\pi ^{2}} 是从大范围值中随机选择的两个数互质的概率极限(无公因数) . 素数在那个大范围内的分布,比如有多少素数小于给定的大数,用素数定理来描述,但是没有已知的第 n 个素数 {\displaystyle n} 的公式。在最基本的形式中,狄利克雷关于加法运算的定理指出线性多项式 p ( n ) a + bn {\displaystyle p(n)a+bn} 与 a {\displaystyle a} 和 b {\displaystyle b} 一起质数对于无限数量的素数。该定理的一种更严格的形式表明,这些质数的倒数之和发散,并且具有相等 b {\displaystyle b} 的不同线性多项式具有大致相同的质数比。关于高阶多项式中素数的比值虽然提出了很多假说,但都没有得到证实,也不清楚是否存在一个二次多项式可以总是给出整数值。

用微积分证明欧几里得定理

欧拉关于无限多个素数存在的证明考虑素数 1 2 + 1 3 + 1 5 + 1 7 + + 1 p 的倒数和。 {\displaystyle {\frac {1}{2}}+{\frac {1}{3}}+{\frac {1}{5}}+{\frac {1}{7}}+\cdots + {\frac {1}{p}}.} 欧拉证明了对于任意实数 x {\displaystyle x},存在一个质数 p {\displaystyle p} 使得总和大于 x {\displaystyle x} 。如果只有有限个素数,这个和必须在最大素数处达到最大值,而不是在 x {\displaystyle x} 的值上增加,所以有无限多个素数。。默滕斯第二定理进一步描述了该总和值的增加率。为了比较,sum 1 1 2 + 1 2 2 + 1 3 2 + + 1 n 2 {\displaystyle {\frac {1}{1^{2}}}+{\frac {1}{2^{2}}} + {\frac {1}{3^{2}}}+\cdots +{\frac {1}{n^{2}}}} 不会随着 n {\displaystyle n} 的增加而增加到无穷大到无穷大(见巴塞尔问题)。在这种情况下,素数比自然数的平方出现得更频繁,即使两个集合都是无限的。布伦定理指出孪生素数的倒数之和 ( 1 3 + 1 5 ) + ( 1 5 + 1 7 ) + ( 1 11 + 1 13) + ⋯ {\displaystyle \left({{\frac {1}{3}}+{\frac {1}{5}}}\right)+\left({{\frac {1}{5}} +{\frac {1}{7}}}\right)+\left({{\frac {1}{11}}+{\frac {1}{13}}}\right)+\cdots } 是有限的。由于这个定理,不可能应用欧拉的方法来证明孪生素数猜想有无穷多对孪生素数。

给定数字以下的素数数

素数计数函数 π ( n ) {\displaystyle \pi (n)} 定义为不大于 n {\displaystyle n} 的素数数。例如, π ( 11 ) 5 {\displaystyle \pi (11)5} ,表示小于或等于11的素数有5个。 有几种方法可以计算π ( n ) {\ displaystyle \pi (n)} 比枚举直到 n {\displaystyle n} 的所有素数更快,例如 Meissel–Lehmer 算法。质数定理指出 π ( n ) {\displaystyle \pi (n)} 渐近于 n / log ⁡ n {\displaystyle n/\log n} 或 π ( n ) ∼ n log ⁡ n , { \displaystyle \ pi (n)\sim {\frac {n}{\log n}},} 表示 π ( n ) {\displaystyle \pi (n)} 与右侧分数的比值变为 1 作为 n {\displaystyle n} 增加到无穷大。跟随那个,随机选择的小于 n {\displaystyle n} 的数是素数的概率与 n {\displaystyle n} 的位数成反比。此外,第 n 个素数 {\displaystyle n} 与 n log ⁡ n {\displaystyle n\log n} 成正比,素数距离的平均长度与 log ⁡ n {\displaystyle \ log n} 成正比。π ( n ) {\displaystyle \pi (n)} 的更精确近似值由补对数积分 π ( n ) ∼ Li ⁡ ( n ) ∫ 2 n d t log ⁡ t 给出。 {\displaystyle \pi (n)\sim \operatorname {Li} (n)\int _{2}^{n}{\frac {dt}{\log t}}.}}}

级别加

等差数列是有限或无限的数字序列,使得序列中的连续数字具有相同的差。该差值称为等差数列的模数(功差)。例如,3, 12, 21, 30, 39,... 是模数为 9 的无穷加法。在等差数列中,所有数除以模数得到相等的余数;在上面的例子中,余数等于 3。因为 9 的模数和 3 的余数都是 3 的倍数,所以序列中的其他元素也是。因此,给定的等差数列只包含一个素数,即数字 3。 一般来说,无限加法 a , a + q , a + 2 q , a + 3 q , ... {\ displaystyle a,a+q,a +2q,a+3q,只有当余数 a {\displaystyle a} 和模数 q {\displaystyle q} 是素数时,\dots } 才能包含多个素数。那么,根据等差数列的狄利克雷定理,等差数列包含无穷多个素数。 Green-Tao 定理表明存在任意长的仅包含素数的有限算术级数。

二次多项式的质值

欧拉注意到函数 n 2 − n + 41 {\displaystyle n^{2}-n+41} 返回一个质数,其中 1 ≤ n ≤ 40 {\displaystyle 1\leq n\leq 40} ,尽管复合值当 n {\displaystyle n} 大于 40 时开始出现。找到对这种现象的解释是 Heegner 数代数数论和数类问题的前提。 Hardy-Littlewood 猜想 F 用对数积分和多项式系数来预测具有整数系数的二次多项式的值中素数的密度。没有经过验证的二次多项式仅适用于素数。Ulam 扭曲将自然数排列成一个二维平面,围绕原点以同心正方形扭曲,并带有标记的素数。在这个例子中很容易看出素数只集中在某些对角线上,这意味着有一些二次多项式比其他的更频繁地给出素数。

zeta 函数和黎曼猜想

黎曼猜想 (1859) 是数学中最著名的未解决问题之一,也是七千年难题之一,它要求找到黎曼 zeta 函数 ζ ( s ) {\displaystyle \zeta (s)} 的解。该函数是复数集上的解析函数。对于实部大于 1 的复数 s {\displaystyle s},它等于所有整数的无穷和和所有素数的无穷积:ζ ( s ) ∑ n 1 ∞ 1 n s ∏ p 素数 1 1 − p − s 。 {\displaystyle \zeta (s)\sum _{n1}^{\infty }{\frac {1}{n^{s}}}\prod _{p{\text{ prime}}}{\frac { 1}{1-p^{-s}}}。} 总和和乘积(由欧拉发现)之间的这种相等称为欧拉乘积。欧拉积可以从算术基本定理中推导出来,它显示了 zeta 函数和素数之间的关系。它导致了无限多个素数存在的另一个证明:如果只有有限个素数,则和和乘积之间的等号也出现在 s 1 {\displaystyle s1} 但和是发散的(即调和级数 1 + 1 2 + 1 3 + ... { \displaystyle 1+{\tfrac {1}{2}}+{\tfrac {1}{3}}+\dots } ) 而积是收敛的(具有有限值),矛盾。黎曼的理论指出zeta 函数都是负偶数或实部为 1/2 的复数。素数定理的原始证明是基于这个猜想的松散形式,即 1 没有实部,尽管还有其他几个更基本的证明。素数计数函数可以用黎曼的显式公式表示为一个和,其中每一项都来自 zeta 函数的根:和的主项是对数积分,其余项导致和的值在那个主要术语。在这种情况下,根会影响素数的分布。如果黎曼猜想是正确的,这种振荡会更小,素数定理给出的素数的渐近分布在更小的区间上也是正确的(长度大致等于 x {\displaystyle x} 的平方根,对于接近数字 x {\显示样式 x} )。

抽象代数

模算术和有限域

模算术是常规算术的另一种形式,它只使用数字 { 0 , 1 , 2 , … , n − 1 } {\displaystyle \{0,1,2,\dots ,n-1\}} 和一个自然数n {\displaystyle n} 称为模数。任何其他自然数都可以通过用除以 n {\displaystyle n} 时的余数替换它来映射到这个系统中。和、差和乘积模数是通过在普通整数的和、差或乘积的除法中执行余数替换来计算的。整数之间的相等性与模算术中的同余概念有关:x {\displaystyle x} 和 y {\displaystyle y} 是全等的(符号 x ≡ y mod n {\displaystyle x\equiv y{\bmod {n}}} )当它们除以 n {\displaystyle n } 等于平衡。但是,在该数字系统中,只有当且仅当模数为素数时,才能除以非零数。例如,模数为 7 时,可以存在除以 3: 2 / 3 ≡ 3 mod 7 {\displaystyle 2/3\equiv 3{\bmod {7}}} ,因为当我们将两边都乘以 3 时,我们会得到正确的表达式 2 ≡ 9 mod 7 {\displaystyle 2\equiv 9{\bmod {7}}} 。但是对于模数 6(它是一个合数),不能被 3 整除:方程 2 / 3 ≡ x mod 6 {\displaystyle 2/3\equiv x{\bmod {6}}} 没有解,因为两边同时乘以3,左边变成2,右边变成0或3。 moduli 只生成环。通过模数运算,可以推导出一些关于素数的定理。例如,费马小定理指出,如果 a ≢ 0 {\displaystyle a\not \equiv 0} (mod p {\displaystyle p} ) 那么 ap − 1 ≡ 1 {\displaystyle a^{p-1}\ equiv 1 } (mod p {\displaystyle p} )。对 {\displaystyle a} 的所有值求和,我们得到方程 ∑ a 1 p − 1 ap − 1 ≡ ( p − 1 ) ⋅ 1 ≡ − 1 ( mod p ) , {\displaystyle \sum _{a1}^{p-1}a^{p-1 }\equiv (p-1)\cdot 1\equiv -1{\pmod {p}},} 当 p {\displaystyle p} 是素数时为真。 Giuga 猜想认为这个方程是 p {\displaystyle p} 是素数的充分条件。根据威尔逊定理,整数 p > 1 {\displaystyle p>1} 是素数当且仅当阶乘 ( p − 1 ) ! {\displaystyle (p-1)!} 与 –1 mod p {\displaystyle p} 一致。对于合数 n r ⋅ s {\displaystyle \;nr\cdot s\;} 那么这个定理就不成立,因为这两个因数之一可以被 n 和 ( n − 1 ) 整除! {\displaystyle (n-1)!} 所以不可能有 ( n − 1 ) !≡ − 1 ( mod n ) {\displaystyle (n-1)!\equiv -1{\pmod {n}}} .

p-adic数

整数 n {\displaystyle n} 的阶 p {\displaystyle p} -adic ν p ( n ) {\displaystyle \nu _{p}(n)} 是 p {\displaystyle p} 在n {\displaystyle n} 的素数分析。这个概念可以推广到有理数:分数 m / n {\displaystyle m/n} 的 p {\displaystyle p} -adic 能级定义为 ν p ( m ) − ν p ( n ) {\displaystyle \nu _{p}(m) - \nu _{p}(n)} 。然后,绝对值 p {\displaystyle p} -adic | | |有理数 q {\displaystyle q} 的 p {\displaystyle |q|_{p}} 是 | | | p p − ν p ( q ) {\displaystyle |q|_{p}p^{-\nu _{p}(q)}} .当一个整数乘以其绝对值 p {\displaystyle p} -adic 时,该整数素数中的因数 p {\displaystyle p} 减少,只留下素数因数不同。就像使用通常的绝对值测量两个实数之间的距离一样,两个有理数之间的距离可以测量为长度 p {\displaystyle p} -adic,即绝对值 p {\ displaystyle p} -adic of这两个数字的差。根据距离的那个定义,当两个数字之间的差可以被 p {\displaystyle p} 的更高次幂整除时,两个数字被称为接近(距离很小)。就像实数由有理数组成,它们之间的距离与有限数量的值相加形成一个完整域一样,距离为 p {\displaystyle p } 的有理数可以扩展到另一个完整域称为数字 p {\displaystyle p} -adic 的域。从它们推断出的等级、绝对值和全域的概念可以推广到代数数域及其范数(从域的乘法群到全序加法群的某些映射) )、绝对值(从该域到实数的某些乘法映射)和位置智能(从给定的密度集扩展到一个完整的域)。如,从有理数集到实数集的扩展是两个数之间的距离是两个数之差的正常绝对值的位置。到加法组的对应映射是该绝对值的对数,尽管它不满足范数的所有要求。根据奥斯特洛夫斯基定理,在自然等价概念之前,实数和 p {\displaystyle p} -adic 数是同阶的,它们的绝对值是规范的、绝对的,并且在集合上唯一定位。 . Hasse 原理允许通过结合有理数位置的解来解决许多关于有理数的问题,再次强调了素数在数论中的重要性。到加法组的对应映射是该绝对值的对数,尽管它不满足范数的所有要求。根据奥斯特洛夫斯基定理,在自然等价概念之前,实数和 p {\displaystyle p} -adic 数是同阶的,它们的绝对值是规范的、绝对的,并且在集合上唯一定位。 . Hasse 原理允许通过结合有理数位置的解来解决许多关于有理数的问题,再次强调了素数在数论中的重要性。到加法组的对应映射是该绝对值的对数,尽管它不满足范数的所有要求。根据奥斯特洛夫斯基定理,在自然等价概念之前,实数和 p {\displaystyle p} -adic 数是同阶的,它们的绝对值是规范的、绝对的,并且在集合上唯一定位。 . Hasse 原理允许通过结合有理数位置的解来解决许多关于有理数的问题,再次强调了素数在数论中的重要性。实数和 p {\displaystyle p} -adic 数具有相同的秩,它们的绝对值是范数、绝对值和在有理数集合上的唯一位置。 Hasse 原理允许通过结合有理数位置的解来解决许多关于有理数的问题,再次强调了素数在数论中的重要性。实数和 p {\displaystyle p} -adic 数具有相同的秩,它们的绝对值是范数、绝对值和在有理数集合上的唯一位置。 Hasse 原理允许通过结合有理数位置的解来解决许多关于有理数的问题,再次强调了素数在数论中的重要性。

戒指中的元素

交换环是定义加法、减法和乘法的代数结构。整数集是一个环,并且该集合中的素数已被推广到具有术语素数和最小元素的环理论。如果环 R {\displaystyle R} 的元素 p {\displaystyle p} 非零,没有逆元(不是单位元素)并且满足条件,则称其为素数:当 p {\displaystyle p} 可以被 R {\displaystyle R} 中两个元素的 xy {\displaystyle xy} 的乘积整除,那么它也可以被两个元素中的至少一个整除 x {\displaystyle x} 和y {\displaystyle y} 。如果一个元素既不是一元元素,也不是其他两个元素的乘积,则称该元素为极小。在整数环中,素数和最小元素形成相同的集合 { ... , − 11 , − 7 , − 5 , − 3 , − 2 , 2 ,3 , 5 , 7 , 11 , ... } 。 {\displaystyle \{\dots ,-11,-7,-5,-3,-2,2,3,5,7,11,\dots \}\,.} 在任何环中,每一个元素都是最少的元素。它的逆命题只在唯一因式分解领域成立,算术基本定理在唯一因式分解领域成立(根据定义)。这种域的一个例子是整数 Z [ i ] {\displaystyle \mathbb {Z} [i]} 的高斯环,a + b i {\displaystyle a+bi} 形式的复数环,其中 i {\displaystyle i} 是虚数单位,a {\displaystyle a} 和 b {\displaystyle b} 是任意整数。该环的素数元素称为高斯素数。整数环中的素数可能不是高斯整数环中的素数;例如,数字 2 可以写成两个高斯素数 1 + i {\displaystyle 1+i} 和 1 − i {\displaystyle 1-i} 的乘积。与 3 mod 4 全等的有理素数(整数环中的素数元素)是高斯素数,但与 1 mod 4 全等的有理素数不是。它是关于两个完美平方和的费马定理的结果,该定理指出奇素数 p {\displaystyle p} 可以表示为两个完美平方和 px 2 + y 2 { \displaystyle px^{2 }+y^{2}} ,因此可以解析为 p ( x + iy ) ( x − iy ) {\displaystyle p(x+iy)(x-iy)} ,仅当 p {\displaystyle p} 与 1 mod 4 一致。

元素理念

并非每个环都是唯一的分解域。例如,在数环 a + b − 5 {\displaystyle a+b{\sqrt {-5}}} (其中 a {\displaystyle a} 和 b {\displaystyle b} 是整数),数 21有两种解析方式: 21 3 ⋅ 7 ( 1 + 2 − 5 ) ( 1 − 2 − 5 ) {\displaystyle 213\cdot 7(1+2{\sqrt {-5}})(1-2{\ sqrt {-5}})} ,所有四个因素都最小,因此它没有单因素分析。为了将唯一因子分析的概念扩展到其他更大的环类,术语编号可以替换为理想的术语,这是一个环中元素的子集,包含每对元素的总和以及每个元素的乘积其元素与环中的元素。素理想是在素元产生的初理想为素理想的情况下对元元进行推广的素理想,是交换代数、代数数论和代数几何中的一个重要和主要的研究课题。整数环中的素理想是 (0), (2), (3), (5), (7), (11),...算术的基本定理被推广到拉斯克-诺特定理,该定理将诺特交换环中的任何理想表示为初等理想的交集,一种概括。适用于素数幂。环的谱是一个几何空间,其点是那个环的主要理想。该术语对代数几何有很大帮助,许多其他相关概念也出现在几何和数论中。例如,当应用于扩展领域时,素理想的分析或除法是代数数论的一个基本问题,类似于几何中的除法。这些概念甚至可以帮助解决数论中涉及整数的一些特殊问题。例如,可以在二次数域的整数环中使用素理想来证明二次互易律,即关于存在平方根表达式模素数的陈述。早期证明费马大定理的尝试导致了正则素数的概念,即与除数整数域中不存在唯一因子分析相关的素数。 Chebotarev密度定理解决了代数数域中有多少素数可以分解成许多素数理想的乘积的问题,当应用于除数圆时,算术中关于素数的狄利克雷定理有一个特例进展。关于平方根表达式模一个素数的存在的陈述。早期证明费马大定理的尝试导致了正则素数的概念,即与除数整数域中不存在唯一因子分析相关的素数。 Chebotarev密度定理解决了代数数域中有多少素数可以分解成许多素数理想的乘积的问题,当应用于除数圆时,算术中关于素数的狄利克雷定理有一个特例进展。关于平方根表达式模一个素数的存在的陈述。早期证明费马大定理的尝试导致了正则素数的概念,即与除数整数域中不存在唯一因子分析相关的素数。 Chebotarev密度定理解决了代数数域中有多少素数可以分解成许多素数理想的乘积的问题,当应用于除数圆时,算术中关于素数的狄利克雷定理有一个特例进展。整数素数涉及在划分圆的整数域中不存在唯一因式分解。 Chebotarev密度定理解决了代数数域中有多少素数可以分解成许多素数理想的乘积的问题,当应用于除数圆时,算术中关于素数的狄利克雷定理有一个特例进展。整数素数涉及在划分圆的整数域中不存在唯一因式分解。 Chebotarev密度定理解决了代数数域中有多少素数可以分解成许多素数理想的乘积的问题,当应用于除数圆时,算术中关于素数的狄利克雷定理有一个特例进展。

群论

在有限群论中,Sylow 定理指出,如果素数 pn {\displaystyle p^{n}} 的幂可以被群的阶整除,那么它就有一个阶 pn {\displaystyle p ^{n }} 。根据拉格朗日定理,具有素数阶的群是循环群,根据伯恩赛德定理,具有可被两个素数整除的数量级的群是可解群。

计算方法

很长一段时间,一般的数论和特别是素数的研究被认为是纯数学的经典例子,当时没有数学以外的应用,除了使用具有质数齿数的齿轮来限制磨损。一些数字理论家,比如英国数学家 GH Hardy 甚至以从事绝对没有军事意义的研究而自豪。这种观点已经被抛弃了多年。1970 年,质数可以用作创建公钥密码算法的基础。这些应用程序有助于促进对素数计算算法和检查数素性方法的研究。最基本的素性检查算法,试除算法,对于非常大的数字来说太慢了。一组现代算法可以应用于任何数字,而对于特殊的数字组,还有更有效的算法。大多数素数检查算法只判断它们的输入是否为素数。其他一些程序也从复合输入中输出一个(或全部)素因数,称为整数解析算法。质数也有作为校验和、哈希表和伪随机数生成器的计算应用程序。其他一些程序也从复合输入中输出一个(或全部)素因数,称为整数解析算法。质数也有作为校验和、哈希表和伪随机数生成器的计算应用程序。其他一些程序也从复合输入中输出一个(或全部)素因数,称为整数解析算法。质数也有作为校验和、哈希表和伪随机数生成器的计算应用程序。

试分算法

测试给定整数 n {\displaystyle n} 素性的最简单方法称为试除算法。该算法将 n {\displaystyle n} 除以从 2 到 n {\displaystyle n} 的平方根的所有整数。当任何整数能被 n {\displaystyle n} 整除时,n {\displaystyle n} 是合数,否则是素数。不需要检查大于该平方根的数字,因为当 n a ⋅ b {\displaystyle na\cdot b} 两个因子 a {\displaystyle a} 和 b {\displaystyle b} 之一小于或等于 n {\displaystyle n} 的平方根。另一种优化形式是仅检查区间中的主要因子。例如,要检查 37 是否为素数,该算法将其除以 2 和 √37 之间的素数,即 2、3 和 5。所有三个除法的余数都不为零,因此 37 是素数。这种方法虽然简单,但在测试大整数的素数时并不实用,因为除法的次数随着整数位数的增加呈指数增长。但是,在对通过该算法的数字应用更复杂的方法之前,仍然使用试除算法来快速找到具有小因子的合数。

在计算机出现之前,许多列出所有质数或解析质数的数字表已广泛发布。最古老的编制素数列表的方法称为埃拉托色尼筛法。右图显示了该方法的最佳形式。另一个解决这个问题的更有效的筛子是阿特金筛子。在高等数学中,筛分理论将类似的方法应用于许多其他问题。

检查素性并证明素性

一些用于解决任何给定 n {\displaystyle n} 的素性问题的最快的现代算法是概率(蒙特卡罗)算法,也就是说,它有很小的随机化机会。如,测试 Solovay–Strassen 给定数 p {\displaystyle p} 随机选择一个数 a {\displaystyle a} 介于 2 和 p − 2 {\displaystyle p-2} 并使用模幂来检查 a ( p − 1 ) / 2 ± 1 {\displaystyle a^{(p-1)/2}\pm 1} 可以被 p {\displaystyle p} 整除。如果是,则回答“是”,否则回答“否”。如果 p {\displaystyle p} 是素数,那么它总是回答“是”,但是如果 p {\displaystyle p} 是复合的,那么它回答“是”的概率最多为 1/2,而“否”的概率至少为 1/ 2.如果这个算法在同一个数上重复 n {\displaystyle n} 次,一个合数每次通过算法的最大概率是 1/2 n {\displaystyle 1/2^{n}} 。由于该概率随着测试执行次数的增加呈指数下降,因此通过迭代算法的数字是素数的概率很高(但不确定)。另一方面,如果一个数没有通过测试,那么它肯定是合数。通过这种测试的合数称为伪素数。相反,其他一些算法保证答案总是正确的:素数总是被确定为素数,合数总是被定义为合数。例如,这个陈述适用于试除算法。保证正确输出的算法包括确定性算法,例如 AKS 素性测试,以及随机选择的算法对结果没有影响的随机拉斯维加斯算法。例如某种形式的椭圆曲线素性证明。当椭圆曲线法得出一个数是素数时,它也会输出一个素数证明,可以快速验证。椭圆曲线技术是算法中最快的,具有绝对精度,但执行时间仅基于实验而不是证明。 AKS 测试具有通过数学推理证实的计算复杂性,但比椭圆曲线技术慢。这些方法可用于通过生成和测试随机数直到找到素数来生成大素数;然后,概率检查算法可以在算法“肯定正确”之前快速消除大部分合数。用于验证剩余的数是否为素数,下表列出了一些这样的算法。正常运行时间由测试次数 n {\displaystyle n} 和迭代次数 k {\displaystyle k}(对于概率算法)给出。此外,ε {\displaystyle \varepsilon } 是任意小的正数,log {\displaystyle \log } 是未定义底的对数。大 O 表示法意味着每个时间间隔必须乘以一个比例常数才能将其从标量转换为时间单位;该常数取决于规范,例如用于实现算法的计算机类型,但不管输入参数 n {\displaystyle n} 和 k {\displaystyle k} 。

特殊算法和最大已知素数

除了上述适用于任何自然数的算法外,一些特殊形式的数也可以更快地进行素性测试。例如,Lucas-Lehmer 检验可以确定梅森数(2 的幂减 1)是否为质数,时间等于 Miller-Rabin 检验的一次迭代。这就是为什么自 1992 年(截至 2018 年 12 月)以来,已知最大的素数一直是梅森素数。假设有无限多个梅森素数,下表列出了各种形式的最大已知素数。其中一些是通过分布式计算发现的。 2009 年,Great Internet Mersenne Prime Search 项目因第一个至少有 1000 万小数位的素数而获得 100,000 美元的奖金。电子前沿基金会还分别为至少 1 亿和 10 亿位数的质数提供 150,000 美元和 250,000 美元的奖金。

整数分析

给定一个合数 n {\displaystyle n} ,输出一个(或全部)素因数的工作称为对 n {\displaystyle n} 的分析。这项任务比检查素性要困难得多,尽管存在许多分析算法,但它们都比检查素性的最快方法慢。试除算法和 RHO 算法可以找到 n {\displaystyle n} 的非常小的因子,椭圆曲线分析算法可以在 n {\displaystyle n} 有倍数的情况下有效,并且中等大。一些适用于与因子大小无关的任何大数的方法包括二阶筛法和普通数值场筛法。与检查素性一样,有许多分析算法需要特殊形式的输入,包括特殊的数字字段筛选。截至 2020 年 2 月,传统算法分析的最大数字是 RSA-250,这是一个 250 位(829 位)的数字,是两个大素数的乘积。Shor 算法允许分析任何具有多项式步数的整数量子计算机。然而,就目前的技术而言,该算法仅适用于非常小的数字。截至 2012 年 10 月,Shor 算法在量子计算机中分析的最大数字是 21。有许多解析算法需要特殊形状的输入,包括特殊的数字字段筛。截至 2020 年 2 月,传统算法分析的最大数字是 RSA-250,这是一个 250 位(829 位)的数字,是两个大素数的乘积。Shor 算法允许分析任何具有多项式步数的整数量子计算机。然而,就目前的技术而言,该算法仅适用于非常小的数字。截至 2012 年 10 月,Shor 算法在量子计算机中分析的最大数字是 21。有许多解析算法需要特殊形状的输入,包括特殊的数字字段筛。截至 2020 年 2 月,传统算法分析的最大数字是 RSA-250,这是一个 250 位(829 位)的数字,是两个大素数的乘积。Shor 算法允许分析任何具有多项式步数的整数量子计算机。然而,就目前的技术而言,该算法仅适用于非常小的数字。截至 2012 年 10 月,Shor 算法在量子计算机中分析的最大数字是 21。Shor 算法允许在量子计算机中分析具有多项式步数的任何整数。然而,就目前的技术而言,该算法仅适用于非常小的数字。截至 2012 年 10 月,Shor 算法在量子计算机中分析的最大数字是 21。Shor 算法允许在量子计算机中分析具有多项式步数的任何整数。然而,就目前的技术而言,该算法仅适用于非常小的数字。截至 2012 年 10 月,Shor 算法在量子计算机中分析的最大数字是 21。

Ứng dụng khác trong điện toán

一些公钥加密算法,例如 RSA 和 Diffie-Hellman 密钥交换,基于大素数(最常见的是 2048 位素数)。 RSA 是基于这样的假设:将两个大数 x {\displaystyle x} 和 y {\displaystyle y} 相乘比计算 x {\displaystyle x} 和 y {\displaystyle y}(假设两个素数在一起)容易得多) 如果只有一个产品 xy {\displaystyle xy} 是已知的。Diffie-Hellman 密钥交换依赖于以下事实:模幂运算有多种有效算法(计算 ab mod c {\displaystyle a^{b}{\bmod {c}}} ),而逆计算(离散对数)是据说是一道难题,质数在哈希表中经常使用。例如,Carter 和 Wegman 的原始通用散列方法基于通过随机选择大素数的线性函数模来计算散列函数。 Carter 和 Wegman 使用大素数的高阶多项式将此方法推广到 k {\displaystyle k} 独立散列。就像在哈希函数中一样,基于二阶检测的哈希表的大小使用质数,以确保元组覆盖整个表,一些校验和方法是基于质数的数学知识。例如,ISBN 中使用的校验和由所有数字(最后一位除外)的总和取模 11 确定。由于 11 是素数,因此该方法可以检测数字错误和相邻数字的转置。 Adler-32,另一个校验和引擎,使用模数算法 65521,最大质数小于 2 16 {\displaystyle 2^{16}} 。素数也用于伪随机数生成器,包括线性全等生成器和 Mersenne Twister。一些校验和方法基于素数的数学知识。例如,ISBN 中使用的校验和由所有数字(最后一位除外)的总和取模 11 确定。由于 11 是素数,因此该方法可以检测数字错误和相邻数字的转置。 Adler-32,另一个校验和引擎,使用模数算法 65521,最大质数小于 2 16 {\displaystyle 2^{16}} 。素数也用于伪随机数生成器,包括线性全等生成器和 Mersenne Twister。一些校验和方法基于素数的数学知识。例如,ISBN 中使用的校验和由所有数字(最后一位除外)的总和取模 11 确定。由于 11 是素数,因此该方法可以检测数字错误和相邻数字的转置。 Adler-32,另一个校验和引擎,使用模数算法 65521,最大质数小于 2 16 {\displaystyle 2^{16}} 。素数也用于伪随机数生成器,包括线性全等生成器和 Mersenne Twister。例如,ISBN 中使用的校验和是通过取所有数字(最后一位除外)之和取模 11 来确定的。由于 11 是素数,因此该方法可以检测数字错误和相邻数字的转置。 Adler-32 是另一种校验和工具,使用模数算法 65521,即小于 2 16 {\displaystyle 2^{16}} 的最大素数。素数也用于伪随机数生成器,包括线性全等生成器和 Mersenne Twister。例如,ISBN 中使用的校验和由所有数字(最后一位除外)的总和取模 11 确定。由于 11 是素数,因此该方法可以检测数字错误和相邻数字的转置。 Adler-32,另一个校验和引擎,使用模数算法 65521,最大质数小于 2 16 {\displaystyle 2^{16}} 。素数也用于伪随机数生成器,包括线性全等生成器和 Mersenne Twister。小于 2 16 {\displaystyle 2^{16}} 的最大素数。素数也用于伪随机数生成器,包括线性全等生成器和 Mersenne Twister。小于 2 16 {\displaystyle 2^{16}} 的最大素数。素数也用于伪随机数生成器,包括线性全等生成器和 Mersenne Twister。

Các ứng dụng khác

素数是数论的核心,在其他数学领域有许多应用,包括抽象代数和基本几何。例如,可以在二维平面上放置质数个点,使得没有三个点共线,或者任何具有三个顶点的三角形都是大的。另一个例子是爱森斯坦标准,它根据素数及其平方的系数的可整性来测试多项式是否最小。素数的概念非常重要,以至于它已被推广到其他数学分支。通常,“主要”在适当时表示“最小”或“不可扩展”。例如,给定域的素域是给定域中同时包含 0 和 1 的最小子域。它可以是有理数域,也可以是元素个数为素数的有限域。第二个含义意味着任何对象都有一个独特的分解,分解为它的主要成分。例如,在结理论中,素结是解析结,也就是说,它不能写成两个非平凡结的联合和。每个任意结都有一个唯一的表示,作为质数结的链接之和。三流形的元素分析是另一个例子,与数学和计算一样,素数与量子力学有关,是艺术和文学中的隐喻。它们在进化生物学中也有应用,以解释蝉科的生命周期。

Đa giác vẽ được và phân chia đa giác

费马数是形式为 F k 2 2 k + 1 , {\displaystyle F_{k}2^{2^{k}}+1,} 的数,其中 k {\displaystyle k} 是一个非负整数。它们以皮埃尔·德·费马(Pierre de Fermat)的名字命名,他曾预言这种形式的所有数都是素数。前五个费马数 - 3, 5, 17, 257 和 65,537 - 都是素数,但 F 5 {\displaystyle F_{5}} 是合数,与所有其他费马数相似(2017 年最多五个)。当且仅当 n {\displaystyle n} 的奇素因数集(如果有)仅由费马素数组成时,才可以用直尺和圆规绘制 n {\displaystyle n} -正则。类似地,当且仅当 n {\displaystyle n} 的质因数集包含数字 2 或数字 3 具有相同(可能为空)一组皮尔庞特素数,形式为 2 a 3 b + 1 {\displaystyle 2^{a}3^{b}+1} 的素数。当 n {\displaystyle n} 是素数的幂时,任何凸多边形都可以分成 n {\displaystyle n} 个较小的面积和周长相等的凸多边形,但性质未知这与其他值相比如何n {\displaystyle n} 。

量子力学

从 1970 年代 Hugh Montgomery 和 Freeman Dyson 的工作开始,许多数学家和物理学家推测黎曼 zeta 函数的根与量子系统的能级有关。由于非零基和 SIC-POVM(完全信息对称正算子度量)等数学结构,素数在量子信息科学中也很重要。

生物

北美蝉超科Magicicada的进化周期与素数有关。这些昆虫大部分时间都以地下幼虫的形式生活。它们仅在 7、13 或 17 年后逐渐生长并钻入地下,最多在几周后飞翔、繁殖和死亡。生物学家假设生殖周期的基本要素是避免与捕食者的周期同步。相比之下,竹子的多年开花期据说是平稳的,其分析的主要因素很少。

艺术和文学

质数影响了许多艺术家和作家。法国作曲家奥利维尔·梅西安 (Olivier Messiaen) 使用质数通过“自然现象”创作音乐。在许多作品中,例如 La Nativité du Seigneur (1935) 和 Quatre études de rythme (1949–1950),他同时应用了由不同素数给出的长度的音乐元素来创造特定的节奏:数字 41、43、47 和 53 出现在第三个练习“Neumes rythmiques”中。根据梅西安的说法,这种构图风格是“受自然运动的启发,朝着自由和差异方向运动”。在科幻小说《接触》(1985)中,科学家卡尔·萨根(Carl Sagan)建议分析元素分析可以用来创造两个与外星人交流时的三维图像平面,他和美国天文学家弗兰克·德雷克 (Frank Drake) 于 1975 年提出的一个想法。 在马克·哈登 (Mark Haddon) 的小说《夜间狗的奇怪事件》中,作者用连续的素数对故事的条目进行编号,以传达主角的心理状态,一个患有阿斯伯格综合症的数学天才男孩。质数是保罗·佐丹奴 (Paolo Giordano) 的小说 La Solitudine dei Numeri Primi(质数的孤独)中对孤独的隐喻,在那里它们被整数描述为“局外人”。作者用连续的素数对故事的条目进行编号,以传达主人公的精神状态,一个患有阿斯伯格综合症的数学天才男孩。素数是保罗·佐丹奴 (Paolo Giordano) 的小说 La Solitudine dei Numeri Primi(素数的孤独)中对孤独的隐喻,在那里它们被整数描述为“局外人”。作者用连续的素数对故事的条目进行编号,以传达主人公的精神状态,一个患有阿斯伯格综合症的数学天才男孩。素数是保罗·佐丹奴 (Paolo Giordano) 的小说 La Solitudine dei Numeri Primi(素数的孤独)中对孤独的隐喻,在那里它们被整数描述为“局外人”。

查看更多

笔记

笔记

外部链接

Hazewinkel, Michiel ed. (2001),“质数”,数学百科全书,斯普林格,ISBN 978-1-55608-010-4 质数(数字)在大英百科全书(英语)印刷节目《我们的时代》由 BBC 制作的质数。Caldwell, Chris, Primes.utm.edu 上的 Prime 页面 越南百科全书的 Prime 表 高达 1 万亿的 Prime