質數分解- 維基百科，自由嘅百科全書

質數分解或質因分解（Prime Factorization），又叫整數分解(integer factorization)，算法基礎、算術基本原理（Fundamental Theorem of Arithmetic），係數論入面一個 ... 質數分解 出自維基百科，自由嘅百科全書 跳去導覽 跳去搵嘢 質數分解由德國數學家高斯嘅《算術研究》用商餘計算嚟證明咗 質數分解或質因分解（PrimeFactorization），又叫整數分解(integerfactorization)，算法基礎、算術基本原理（FundamentalTheoremofArithmetic），係數論入面一個基本概念，亦可以喺抽象代數入面應用。

質數分解指嘅係每一個自然數或者整數，都可以寫成一堆質數嘅乘法。

證明質數分解成立需要用到質數嘅定義、可除性等工具。

例子： 2016 = 2 × 2 × 2 × 2 × 2 × 3 × 3 × 7 = 2 5 × 3 2 × 7 {\displaystyle2016=2\times2\times2\times2\times2\times3\times3\times7=2^{5}\times3^{2}\times7} 根據質數分解定理，任何一個大過1嘅正整數，就可以寫成一堆質數嘅乘法，而對應呢個數嘅寫法係獨一無二嘅，即係對於每一個正整數 k : k ∈ N ∖ { 1 } {\displaystylek:k\in\mathbb{N}\setminus\{1\}} ，都可以寫成 k = p 1 a 1 p 2 a 2 p 3 a 3 ⋯ p n a n : { a 1 , a 2 , a 3 ⋯ a n } ∈ N {\displaystylek={p_{1}}^{a_{1}}{p_{2}}^{a_{2}}{p_{3}}^{a_{3}}\cdots{p_{n}}^{a_{n}}:\{a_{1},a_{2},a_{3}\cdotsa_{n}\}\in\mathbb{N}} ，而 p 1 , p 2 , p 3 , ⋯ , p n {\displaystylep_{1},p_{2},p_{3},\cdots,p_{n}} 都係質數。

目錄 1證明 1.1存在性 1.2獨特性 2應用 3睇埋 證明[編輯] 存在性[編輯] 假設最少有一個數 n ∈ N {\displaystylen\in\mathbb{N}} 係唔可以被寫成一堆質數嘅乘法。

因為 N {\displaystyle\mathbb{N}} 嘅排序性質，所以係有一個最細既 a ∈ N {\displaystylea\in\mathbb{N}} 係唔可以被寫成一堆質數嘅乘法。

如果 a {\displaystylea} 係質數，咁 a = a {\displaystylea=a} 就係寫成一堆質數嘅乘法。

如果 a {\displaystylea} 唔係質數，咁要係有一個 b , c {\displaystyleb,c} 符合 a = b c {\displaystylea=bc} 。

因為 a {\displaystylea} 係最細符合條件：「唔可以被寫成一堆質數嘅乘法」，所以 b , c {\displaystyleb,c} 可以被寫成一堆質數嘅乘法。

但係因為 a = b c {\displaystylea=bc} ，所以 a {\displaystylea} 可以被寫成一堆質數嘅乘法。

獨特性[編輯] 假設 a > 1 ∈ N {\displaystylea>1\in\mathbb{N}} 可以質數分解成 a = p 1 ⋯ p m = q 1 ⋯ q n {\displaystylea=p_{1}\cdotsp_{m}=q_{1}\cdotsq_{n}} ，而 p i , q i {\displaystylep_{i},q_{i}} 都係質數。

因為 p 1 | a {\displaystylep_{1}|a} ，所以 p 1 | q 1 ⋯ q n {\displaystylep_{1}|q_{1}\cdotsq_{n}} 。

利用歐幾理得推論，因為 p 1 {\displaystylep_{1}} 係質數，所以 p 1 | q j {\displaystylep_{1}|q_{j}} 。

同一個原理，可以得知會有一個 q j | p 1 {\displaystyleq_{j}|p_{1}} 。

所以 p 1 = q j {\displaystylep_{1}=q_{j}} ，為咗簡化，會將 q j {\displaystyleq_{j}} 寫成 q 1 {\displaystyleq_{1}} ，所以 p 1 = q 1 {\displaystylep_{1}=q_{1}} 。

之後約簡得出， p 2 ⋯ p m = q 2 ⋯ q n {\displaystylep_{2}\cdotsp_{m}=q_{2}\cdotsq_{n}} 。

因為 a {\displaystylea} 係第一個，即係最細嘅自然數係有兩個唔同嘅質數分解，而 p 2 ⋯ p m < a {\displaystylep_{2}\cdotsp_{m}