第4問

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

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

とする。集合

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

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

a

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

b

の最小値を求めよ。

ステップ 4/5: 中国剰余定理により

b=6

を構成する

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

ざっくり言うと

$\{a+1,\dots,a+6\}$ の中の3組の特定のペアがそれぞれ必要な剰余を満たすように $a$ を選ぶと、間隔- $2$ 、間隔- $3$ 、間隔- $4$ の一致がちょうど1つずつ実現し、今度は有効なペアリングで6個の頂点すべてを覆うのに十分となる。

a{+}1\equiv7,\ a{+}5\equiv11\!\!\pmod{19};\quad a{+}2\equiv2,\ a{+}4\equiv4\!\!\pmod7;\quad a{+}3\equiv1,\ a{+}6\equiv1\!\!\pmod3

詳しい解説

中国剰余定理により、 $a$ を（互いに素な法 $3,7,19$ に定理を適用すると無限に多く存在する） $a+1\equiv7\pmod{19}$ かつ $a+5\equiv11\pmod{19}$ （これにより $19\mid\gcd(P(a+1),P(a+5))$ となり、間隔- $4$ のペアとなる）、 $a+2\equiv2\pmod7$ かつ $a+4\equiv4\pmod7$ （これにより $7\mid\gcd(P(a+2),P(a+4))$ となり、間隔- $2$ のペアとなる）、そして $a+3\equiv1\pmod3$ かつ $a+6\equiv1\pmod3$ （これにより $3\mid\gcd(P(a+3),P(a+6))$ となり、間隔- $3$ のペアとなる）を同時に満たすように選ぶ。