從平方和談起

分解平方和

在歷史上,人們注意到,型如 4k+1 的自然數 N 若只有一個方法表示成兩互素 (Coprime) 之數的平方和 (Sum of Squares),則 N 是一素數 (Prime Number) 或素數的平方;如果 N 不能表示成平方和,則 N 是合數 (Composite Number) 且含有偶數個型如 4n-1 的素因子,但不能肯定其中有否型如 4n+1 的素因子。

如果 N 可以有兩種或以上的方法表示成兩互素之數的平方和,則我們可以利用下法去分解整數  N:

N = a2 + b2 = c2 + d2

即 N = (ad + bc) (ad - bc) / (a + c) (a - c) 或 N = (ad + bc) (ad - bc) / (d + b) (d - b)

原因很簡單:

N = a2 + b2 則 d2N = a2d2 + b2d2 ,以及

N = c2 + d2 則 b2N = b2c2 + b2d2

兩式相加 (b2 - d2)N = (a2d2 - b2c2) ,把式兩邊除以 (b2 - d2) 再分解便得上式。這便是我們所謂的歐拉分解法 (Euler's Factorization Method)。

 

讓我們看看一實際例子吧:分解 16000001。

設 N = 16000001,則 N = 40002 + 12 = 10492 + 38602,所以

N = (4000*1049 + 3860*1) (4000*1049 - 3860*1) /[ (1049+1) (1049-1)] = 229*69869,其中 229 是素數。

而 69869 = 2622 + 152 = 2682 + 1152,則我們利用上述方法可得:69896 = 109 * 641,而這兩數皆為素數。

所以 16000001 = 109 * 229 * 641

我們不難知道這三個 16000001 的素因子皆是型如 4k+1 的。

 

多了一個 k

後來有人把上法改進,推廣至 x2 + ky2 的型式。如果某數可分柝為一個數的平方和另一數的平方的 k 倍之和,且有兩種或以上的分柝方法,則我們可把它分解:

事實上,如果 N = a2 + kb2 = c2 + kd2,則

即 N = (ad + bc) (ad - bc) / (a + c) (a - c) 或 N = (ad + bc) (ad - bc) / (d + b) (d - b),證法和上式相類似,恕不加冗述。

例:分解 36661。此數肯定已不含較小的素因子如 2、3 、5 、7 、 11 、 13等。

設 N = 36661 = 1692 + 4*452 = 1192 + 4*752

應用上式,N = (167*75 + 45*119) (167*75 + 45*119) / [(169 + 119) (169 - 119)] = 61 * 601

此兩數皆是素數。因此分解便告完成。

 

在二次型式 x2 + ky2 中,令 k 取一些特定數值,如 k=4或 2、-2時,我們來看看分解出來的產物是屬於什麼型式?顯然在 x2 + 4y2 將導致 8n+1 或 8n+5 的型式的因子 (Factor) 出現,而 x2 + 2y2 導致 8n+1 或 8n+3 的型式的因子走出來,而 x2 - 2y2 則會導致 8n+1 或 8n+7 的型式的因子現身。

另外我們把 n = 45677 拿來看看如何減少測試的數:由於這是屬於 8n+5 的型式,故取 k = 4,即二次形 x2 + 4y2

由此令 y =[(45677 - x2) / 4] 1/2 ,從而計出 y < 107。

再加上一些二次剩餘 (Quadratic Residue) 的知識,我們便可把搜索範圍縮小至 7、17、23、27、53、67 和 77 七數,一一試之。

得 45677 = 2112 + 4*172 的表達式,但只有一條,故 45677 是素數。

 

參考文獻及網址

Weisstein, E. W. "Euler's Factorization Method." From MathWorld. http://mathworld.wolfram.com/EulersFactorizationMethod.html.

 

 

Free Web Hosting