已知 $P(n)=n^2 +n+1$.对于任意正整数 $a,b$,若集合$$\{P(a),P(a+1),P(a+2),\ldots,P(a+b)\}$$的每个元素均与其他元素的乘积不互素,则称此集合为"芳香的".求芳香集合中元素个数的最小值.
【难度】
【出处】
2016IMO Short List
【标注】
【答案】
所求最小值为 $6$.
先证明三个引理.
引理1:对于任意整数 $n$,均有$$(P(n),P(n+1))=1$$引理(1)的证明:
$(P(n),P(n+1))=(n^2 +n+1,n^2 +3n+3)=(n^2 +n+1,2n+2)=(n^2 +n+1,n+1)=(1,n+1)=1$.
引理2:对于 $n\not \equiv 2\pmod{7}$,有$$(P(n),P(n+2))=1$$对于 $n\equiv 2\pmod{7}$,有$$(P(n),P(n+2))=7$$引理(2)的证明:由于$$(2n+7)P(n)-(2n-1)P(n+2)=14$$且 $P(n)$ 为奇数,则 $(P(n),P(n+2))$ 必为 $7$ 的因数.
对 $n=0,1,\ldots,6\pmod{7}$,直接验证即得结论成立.
引理3:
对于 $n\not \equiv 1\pmod{3}$,
有$$(P(n),P(n+3))=1$$对于 $n\equiv 1\pmod{3}$,
有$$3~|~(P(n),P(n+3))$$引理(3)的证明:由于$$(n+5)P(n)-(n-1)P(n+3)=18$$且 $P(n)$ 为奇数,则 $(P(n),P(n+3))$ 必为 $9$ 的因数.对 $n=0,1,2\pmod{3}$,直接验证即得结论成立.引理(1),(2),(3)得证.
假设存在一个芳香集合最多有五个元素.可假设其恰包含元素 $P(a),P(a+1),\ldots,P(a+4)$.这是因为接下来的证明对于少于五个元素仍然成立.由引理(1),知 $P(a+2)$ 与 $P(a+1),P(a+3)$ 均互素.不失一般性,假设 $(P(a),P(a+2))>1$.由引理(2)知 $a\equiv 2\pmod{7}$.由于 $a+1\equiv 3\pmod{7}$,由引理(2)知$$(P(a+1),P(a+3))=1$$又集合是芳香的,则 $(P(a),P(a+3))$ 及 $(P(a+1),P(a+4))$ 均大于 $1$.由引理(3)知 $a\equiv 1\pmod{3}$ 且 $a+1\equiv 1\pmod{3}$.矛盾.
下面构造一个有六个元素的芳香集.由中国剩余定理,知存在正整数 $a$,使得 $a\equiv 7\pmod{19}$,$a+1\equiv 2\pmod{7}$,$a+2\equiv 1\pmod{3}$.例如,$a=197$.由引理(2),知 $P(a+1),P(a+3)$ 均能被 $7$ 整除.由引理(3),知 $P(a+2),P(a+5)$ 均能被 $3$ 整除.又 $19~|~P(7)=57$,$19~|~P(11)=133$,则 $P(a),P(a+4)$ 均能被 $19$ 整除.这表明,$\{P(a),P(a+1),\ldots,P(a+5)\}$ 是芳香集.故芳香集合中元素个数的最小值为 $6$
先证明三个引理.
引理1:对于任意整数 $n$,均有$$(P(n),P(n+1))=1$$引理(1)的证明:
$(P(n),P(n+1))=(n^2 +n+1,n^2 +3n+3)=(n^2 +n+1,2n+2)=(n^2 +n+1,n+1)=(1,n+1)=1$.
引理2:对于 $n\not \equiv 2\pmod{7}$,有$$(P(n),P(n+2))=1$$对于 $n\equiv 2\pmod{7}$,有$$(P(n),P(n+2))=7$$引理(2)的证明:由于$$(2n+7)P(n)-(2n-1)P(n+2)=14$$且 $P(n)$ 为奇数,则 $(P(n),P(n+2))$ 必为 $7$ 的因数.
对 $n=0,1,\ldots,6\pmod{7}$,直接验证即得结论成立.
引理3:
对于 $n\not \equiv 1\pmod{3}$,
有$$(P(n),P(n+3))=1$$对于 $n\equiv 1\pmod{3}$,
有$$3~|~(P(n),P(n+3))$$引理(3)的证明:由于$$(n+5)P(n)-(n-1)P(n+3)=18$$且 $P(n)$ 为奇数,则 $(P(n),P(n+3))$ 必为 $9$ 的因数.对 $n=0,1,2\pmod{3}$,直接验证即得结论成立.引理(1),(2),(3)得证.
假设存在一个芳香集合最多有五个元素.可假设其恰包含元素 $P(a),P(a+1),\ldots,P(a+4)$.这是因为接下来的证明对于少于五个元素仍然成立.由引理(1),知 $P(a+2)$ 与 $P(a+1),P(a+3)$ 均互素.不失一般性,假设 $(P(a),P(a+2))>1$.由引理(2)知 $a\equiv 2\pmod{7}$.由于 $a+1\equiv 3\pmod{7}$,由引理(2)知$$(P(a+1),P(a+3))=1$$又集合是芳香的,则 $(P(a),P(a+3))$ 及 $(P(a+1),P(a+4))$ 均大于 $1$.由引理(3)知 $a\equiv 1\pmod{3}$ 且 $a+1\equiv 1\pmod{3}$.矛盾.
下面构造一个有六个元素的芳香集.由中国剩余定理,知存在正整数 $a$,使得 $a\equiv 7\pmod{19}$,$a+1\equiv 2\pmod{7}$,$a+2\equiv 1\pmod{3}$.例如,$a=197$.由引理(2),知 $P(a+1),P(a+3)$ 均能被 $7$ 整除.由引理(3),知 $P(a+2),P(a+5)$ 均能被 $3$ 整除.又 $19~|~P(7)=57$,$19~|~P(11)=133$,则 $P(a),P(a+4)$ 均能被 $19$ 整除.这表明,$\{P(a),P(a+1),\ldots,P(a+5)\}$ 是芳香集.故芳香集合中元素个数的最小值为 $6$
【解析】
略
答案
解析
备注