素因子

(重定向自质因数

素因子(prime factor)或称素因数素因式,在数论里是指能整除给定正整数素数。根据算术基本定理,不考虑排列顺序的情况下,每个正整数都能够以唯一的方式表示成它的素因数的乘积。两个没有共同素因子的正整数称为互素。因为1没有素因子,1与任何正整数(包括1本身)都是互素。只有一个素因子的正整数为素数。

将一个正整数表示成素因数乘积的过程和得到的表示结果叫做素因数分解。显示素因数分解结果时,如果其中某个素因数出现了不止一次,可以用幂次的形式表示。例如360的素因数分解是:

其中的素因数2、3、5在360的素因数分解中的幂次分别是3,2,1。

数论中的不少函数与正整数的素因子有关,比如取值为n的素因数个数的函数和取值为n的素因数之和的函数。它们都是加性函数,但并非完全加性函数。

例子

编辑
  • 1没有素因子。
  • 5只有1个素因子,5本身。(5是素数。)
  • 6的素因子是2和3。(  
  • 2、4、8、16等只有1个素因子:2(2是素数,4 = 22,8 = 23,如此类推。)
  • 100有2个素因子:2和5。(  
  • 143也有2个素因子:11和13。(  [1]
  • 30则有3个素因子:2、3和5。(  

完全平方数

编辑

完全平方数是指等于某个正整数的平方的数。比如225 = 152是完全平方数,而226不是。完全平方数的素因数分解中,每个素因数的幂次都是偶数,这是因为假设完全平方数 ,则它的素因数分解可以从n的素因数分解推出[2] 。假设n的素因数分解是:

 

那么M的素因数分解就是:

 

所以每个素因子的幂次都是 的形式,是偶数。

举例来说,144是一个完全平方数:144 = 122,它的素因数分解是:

 

类似地可以证明,如果某个正整数是完全立方数或某个正整数的幂次: ,那么它的所有素因子的幂次都是d的倍数。

互质关系

编辑

互质是两个正整数之间的一种关系。如果两个正整数ab没有共同的素因子,就称这两个正整数互质。一般来说两个正整数的最大公约数是指能够同时整除两者的正整数之中最大的一个。如果ab有公共的素因子p,那么它们的最大公约数gcd(a, b)就是p的倍数。ab互质则说明最大公约数是1.

Ω函数

编辑

数论函数中与素因数有关的函数包括Ω函数和ω函数。ω函数定义为正整数n不同素因子的个数,而Ω函数定义为计算每个素因数的幂次后正整数n的不同素因子的个数。

 

例如420的素因数分解是:

 

所以ω(420)   4,而Ω(420)   2×1 + 1 + 1 + 1   5. 因为420的素因数分解中2的幂次是2而其余素因子的幂次是1.

参见

编辑

参考来源

编辑
  1. ^ 143 is largest number yet to be factored by a quantum algorithm. [2024-01-01]. (原始内容存档于2023-11-28). 
  2. ^ Sinha Nishit K. Demystifying Number System: (Practical Concepts and Their Applications) for the CAT and Other MBA Exams. Pearson Education India. ISBN 9788131754436 (英语). p.205