質因數

素因子(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