第4問

少なくとも2個の要素を持ち、各要素がほかの要素の少なくとも一つと共通の素因数を持つとき、その正の整数の集合を 芳香的 であるという。

P(n)=n^2+n+1

とする。集合

\{P(a+1),P(a+2),\dots,P(a+b)\}

が芳香的となるような非負整数

a

が存在するような正の整数

b

の最小値を求めよ。

ステップ 1/5: ユークリッドの互除法による4つの鋭い評価

前のステップ次のステップ

ざっくり言うと

$P(n+d)-P(n)$ は $n$ と $d$ に関する単純な多項式であるから、 $P(n)$ とこの差にユークリッドの互除法を適用すると、最大公約数は $d$ のみに依存する小さな固定された約数に定まる。

\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)=n^2+n+1$ であるから、各間隔 $d$ について $P(n+d)-P(n)=d(2n+d+1)$ が計算できる。ユークリッドの互除法を実行する（ $P(n)\equiv0$ を用いて $n$ を消去する）と、すべての整数 $n$ に対して $\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$ であることが分かる。