质数
只能被1和自身整除且大於1的自然數 / 维基百科,自由的 encyclopedia
质数(Prime number),又称素数,指在大于1的自然数中,除了1和该数自身外,无法被其他自然数整除的数(也可定义为只有1与该数本身两个正因数的数)。大于1的自然数若不是质数,则称之为合数(也称为合成数)。例如,5是个质数,因为其正因数只有1与5。7是个质数,因为其正因数只有1与7。而4则是个合数,因为除了1与4外,2也是其正因数。6也是个合数,因为除了1与6外,2与3也是其正因数。算术基本定理确立了质数于数论里的核心地位:任何大于1的整数均可被表示成一串唯一质数之乘积。为了确保该定理的唯一性,1被定义为不是质数,因为在因式分解中可以有任意多个1(如3、1×3、1×1×3等都是3的有效因数分解)。
各种各样的数 |
基本 |
延伸 |
其他 |
古希腊数学家欧几里得于公元前300年前后证明有无限多个质数存在(欧几里得定理)。现时人们已发现多种验证质数的方法。其中试除法比较简单,但需时较长:设被测试的自然数为,使用此方法者需逐一测试2与之间的质数,确保它们无一能整除。对于较大或一些具特别形式(如梅森数)的自然数,人们通常使用较有效率的演算法测试其是否为质数(例如282589933-1是直至2024年4月为止已知最大的梅森质数[1],也是直至2024年4月为止已知最大的质数)。虽然人们仍未发现可以完全区别质数与合数的公式,甚至研究质数分布时相当有力的筛法也会碰到奇偶性问题(也就是多种筛法都无法区别质数跟两个质数相乘的合数的问题),但已建构了质数的分布模式(亦即质数在大数时的统计模式)。19世纪晚期得到证明的质数定理指出:一个任意自然数n为质数的机率反比于其数位(或的对数)。
许多有关质数的问题依然未解,如哥德巴赫猜想(每个大于2的偶数可表示成两个素数之和)及孪生质数猜想(存在无穷多对相差2的质数)。这些问题促进了数论各个分支的发展,主要在于数字的解析或代数方面。质数被用于资讯科技里的几个程序中,如公钥加密利用了难以将大数分解成其质因数之类的性质。质数亦在其他数学领域里形成了各种广义化的质数概念,主要出现在代数里,如质元素及质理想。