歐利費奧利分解法

我們知道平方差 (Difference of Squares) 即 a2 - b2 可以分解 為 (a - b) * (a + b),但基本上平方和 (Sum of Squares) 是不可分解的。但更高次方的和式又如何呢?

在 1873 年,數學家歐利費奧利 (Leon Francois Antonie Aurifeuille) 提出了一種分解法針對一些方冪 (Power) 再加上 1 的數值,這我們稱為 歐利費奧利分解法 (Aurifeuillian Factorization),讓本文為大家作個介紹吧!

我們從 258 + 1 的分解結果

258 + 1 = (229 + 215 + 1) (229 - 215 + 1)

可以歸結出下式:

24k-2 + 1 = (22k-1 + 2k + 1) (22k-1 - 2k + 1)

數學家歐利費奧利集中研究上式當 k = 14的情況,而分解的通法則由盧卡斯 (Edouard Lucas, 1842 - 1891) 提證。

 

下表列寫了一些較小的 k 值的分解情況:

k 24k-2 + 1 22k-1 + 2k + 1 22k-1 - 2k + 1
1 5 5 1
2 65 13 5
3 1025 41 25
4 16385 145 113
5 262145 545 481
6 4194305 2113 1985
7 67108865 8321 8065
8 1073741825 33025 32513
9 17179869185 131585 130561
10 274877906945 525313 523265

 

後來,數學家以不同的底建構相類似的公式:

36k-3 + 1 = (32k-1 + 1) (32k-1 + 3k + 1) (32k-1 - 3k + 1)

510k-5 - 1 = (52k-1 - 1) (54k-2 - 53k-1 + 3*52k-1 - 5k + 1) (54k-2 + 53k-1 + 3*52k-1 + 5k + 1)

如分解 10460353204 ,即 321 + 1 = (37 + 1) (37 + 34 + 1) (37 - 34 + 1) = 2188 * 2269 * 2107。

又如分解 298023223876953124, 525 - 1 = (55 - 1) (510 - 58 + 3*55 - 53 + 1) (510 + 58 + 3*55 + 53 + 1) = 3124 * 9384251 * 10165751。

當然這方法只是分解的第一步,各因子或可以再進一步分解的。

 

參考文獻及網址

Weisstein, E. W. "Aurifeuillean Factorization." From MathWorld. http://mathworld.wolfram.com/AurifeuilleanFactorization.html.

Wells, D. "Aurifeuillian Factorization." From The Most Mysterious Figures in Math - Prime Numbers" , New Jersey: John Wiley & Sons, Inc. pp 14-15, 2005