歐利費奧利分解法

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

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

我們從 2⁵⁸ + 1 的分解結果

2⁵⁸ + 1 = (2²⁹ + 2¹⁵ + 1) (2²⁹ - 2¹⁵ + 1)

可以歸結出下式：

2^4k-2 + 1 = (2^2k-1 + 2^k + 1) (2^2k-1 - 2^k + 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

　

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

3^6k-3 + 1 = (3^2k-1 + 1) (3^2k-1 + 3^k + 1) (3^2k-1 - 3^k + 1)

5^10k-5 - 1 = (5^2k-1 - 1) (5^4k-2 - 5^3k-1 + 3*5^2k-1 - 5^k + 1) (5^4k-2 + 5^3k-1 + 3*5^2k-1 + 5^k + 1)

如分解 10460353204 ，即 3²¹ + 1 = (3⁷ + 1) (3⁷ + 3⁴ + 1) (3⁷ - 3⁴ + 1) = 2188 * 2269 * 2107。

又如分解 298023223876953124， 5²⁵ - 1 = (5⁵ - 1) (5¹⁰ - 5⁸ + 3*5⁵ - 5³ + 1) (5¹⁰ + 5⁸ + 3*5⁵ + 5³ + 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