【习题研讨】122. (a+b) 的 7 次幂减去 a,b 两数的 7 次幂 与 奥里弗耶分解(Aurifeuillean factorization)

证明: 对所有的非负整数  是至少  个素数 ( 不一定互不相同 ) 的乘积. ( 第 36 届美国数学奥林匹克题 )

不少同学想到了归纳，但是最后这题没人做对. 题目涉及到奥里弗耶分解（Aurifeuillean factorization）. 数学应当是简单和美的，如果不是，那是我们理解得还不够！

搜索：在数论中，奥里弗耶分解（Aurifeuillean factorization），以莱昂-弗朗索瓦-安托万·奥里弗耶（Léon-François-Antoine Aurifeuille）的名字命名，是指分圆多项式某些整数值的分解。

由于分圆多项式是整数上的不可约多项式，因此这种分解不能通过多项式的代数分解得到。然而，某些由分圆多项式产生的整数族的分解可以用适用于整个整数族的公式来表示.

https://en.wikipedia.org/wiki/Aurifeuillean_factorization

因式分解：. 直接用二项式定理打开，提取  后剩下的那个四次多项式的分解是经典的，略去不表.

证明 对  用数学归纳法. 当  时,  ,结论成立.

假设当  时,结论成立,即  至少是  个素数的乘积.

当  时, 记 ,  显然  是正整数 ,记 ,  本题归结为证明代数式  是一个合数（它提供至少两个素因数），于是  至少是  个素数的乘积.

但可惜的是：

而

除去因子  后，得到

因此它是第 (14) 个分圆多项式，在整数上是不可以在进行因式分解（可以平移后用艾森斯坦判别法进行判定），这样就没法做下去了. 

注意到  为  的奇数次方，我们可以使用奥里弗耶分解:

事实上,上式右端的两个因子都大于 1 , 只需对较小的一个进行检验.

注意到  ,则

这表明,  是一个合数,结论成立.  

设,证明: 数是一个合数.

解答：当  为偶数时，读者自证. 若  为奇数,设(用到),记,则

上式右边两个数均大于 1,故亦为合数.

综上可知,命题成立.

奥里弗耶分解的核心思想是：某些分圆多项式虽然在整数系数多项式环中不可约，但在代入特殊整数后，可以利用平方差进行整数分解。常见形式是

当  恰好是平方数时，右端便可继续分解为两个整数因子。相关背景可参考 Aurifeuillean factorization[https://en.wikipedia.org/wiki/Aurifeuillean_factorization] 及 Brent 对这类分解的整理 Aurifeuillean factorizations[https://maths-people.anu.edu.au/brent/pub/pub127.html].

当  时，记 ,

特别地，当  是素数时， 也是  因数.

当  时，记 ,

特别地，当  是素数时， 也是  因数.