MathLabs

第4题

如果一个正整数集合至少包含两个元素，且其中每个元素都与其他至少一个元素有公共素因数，就称这个集合是芳香的。设 P(n)=n2+n+1P(n)=n^2+n+1。求最小的正整数 bb，使得存在非负整数 aa，使集合 {P(a+1),P(a+2),…,P(a+b)}\{P(a+1),P(a+2),\dots,P(a+b)\} 是芳香的。
第 1/5 步：四个由欧几里得算法给出的精确界
上一步下一步
通俗地说

由于 P(n+d)−P(n)P(n+d)-P(n) 是关于 nn 和 dd 的简单多项式，对 P(n)P(n) 与这个差运用欧几里得算法，就能把最大公约数限定为仅依赖于 dd 的一个固定的小约数。

gcd⁡(P(n),P(n+1))=1,  gcd⁡(P(n),P(n+2))∣7,  gcd⁡(P(n),P(n+3))∣3,  gcd⁡(P(n),P(n+4))∣19\gcd(P(n),P(n{+}1))=1,\ \ \gcd(P(n),P(n{+}2))\mid7,\ \ \gcd(P(n),P(n{+}3))\mid3,\ \ \gcd(P(n),P(n{+}4))\mid19
详细分析

由于 P(n)=n2+n+1P(n)=n^2+n+1，对每个间隔 dd 可算得 P(n+d)−P(n)=d(2n+d+1)P(n+d)-P(n)=d(2n+d+1)。运用欧几里得算法（利用 P(n)≡0P(n)\equiv0 消去 nn）可知，对所有整数 nn 都有 gcd⁡(P(n),P(n+1))=1\gcd(P(n),P(n+1))=1，gcd⁡(P(n),P(n+2))∣7\gcd(P(n),P(n+2))\mid7，gcd⁡(P(n),P(n+3))∣3\gcd(P(n),P(n+3))\mid3，以及 gcd⁡(P(n),P(n+4))∣19\gcd(P(n),P(n+4))\mid19。