質因數(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