Parfum op getallen?

Opgave - IMO 2016 dag 2 vraag 1

Een verzameling positieve gehele getallen noemen we welriekend als die uit minstens twee elementen bestaat en elk van de elementen een priemdeler gemeen heeft met één van de andere elementen. Definieer $P(n)=n^2+n+1$. Wat is het kleinst mogelijke gehele getal $b \ge 1$ zodanig dat er een geheel getal $a \ge 0$ bestaat waarvoor de verzameling $\{P(a+1),P(a+2),\ldots, P(a+b)\}$ welriekend is?

Oplossing

We zullen bewijzen dat $b=6$.

Eerst bewijzen we volgende lemma's:

Lemma 1: $P(n)$ is oneven.

Dit volgt uit het feit dat $n^2+n$ even is.

Lemma 2: $ggd(P(n),P(n+1))=1$.

Bewijs: Merk op dat $P(n+1)=P(n)+2n+2$.

Dus: $ggd(P(n),P(n+1))$
$=ggd(P(n),2n+2)$
$=ggd(P(n),n+1)$ ($P(n)$ is oneven)
$=ggd(n^2,n+1)$
$=1$.

Lemma 3: $ggd(P(n),P(n+2))>1 \Leftrightarrow n \equiv 2 \pmod 7$.

We bewijzen de twee deelstellingen apart:

1 $ggd(P(n),P(n+2))>1 \Leftarrow n \equiv 2 \pmod 7$

$P(n)=n^2+n+1 \equiv 4+2+1 \equiv 0 \equiv 2+4+1 \equiv (n+2)^2+n+2+1 \pmod 7$.

Dus $ggd(P(n),P(n+2)) \geq 7$.

2 $ggd(P(n),P(n+2))>1 \Rightarrow n \equiv 2 \pmod 7$

$ggd(P(n),P(n+2))$
$=ggd(P(n),4n+6)$ (Merk namelijk op dat $P(n+2)=P(n)+4n+6$)
$=ggd(P(n),2n+3)$ ($P(n)$ is oneven)
$>1$

Uit de laatste twee regels volgt dat er een oneven priemgetal $p$ (want $P(n)$ is oneven) bestaat zodat:
$P(n) \equiv 2n+3 \equiv 0 \pmod p$
$\Rightarrow n \equiv \frac{p-3}{2} \pmod p$ ($p$ is oneven)
$\Rightarrow (\frac{p-3}{2})^2+\frac{p-3}{2}+1 \equiv 0 \pmod p$
$\Leftrightarrow \frac{p^2-4p+3}{4} \equiv -1 \pmod p$
$\Leftrightarrow 0 \equiv p(p-4) \equiv -7 \pmod p$
$\Leftrightarrow p=7$

Daaruit volgt dus ook dat $n \equiv 2 \pmod 7$, waarmee het lemma bewezen is.

Lemma 4: $ggd(P(n),P(n+3))>1 \Leftrightarrow n \equiv 1 \pmod 3$.

We geven terug een bewijs in twee delen:

1 $ggd(P(n),P(n+3))>1 \Leftarrow n \equiv 1 \pmod 3$

$P(n) \equiv 1+1+1 \equiv 0 \equiv P(n+3) \pmod 3$. Dus $ggd(P(n),P(n+3)) \geq 3$.

2 $ggd(P(n),P(n+3))>1 \Rightarrow n \equiv 1 \pmod 3$

Veronderstel dat $n \not\equiv 1 \pmod 3$. Dan zal $P(n) \not\equiv 0 \pmod 3$ en dus $ggd(P(n),3)=1$. Hieruit volgt dat:

$ggd(P(n),P(n+3))$
$=ggd(P(n), 6(n+2))$ (Merk op dat $P(n+3)=P(n)+6(n+2)$)
$=ggd(P(n), n+2)$ ($P(n)$ is oneven en $ggd(P(n),3)=1$)
$=ggd(n^2-1,n+2)$
$=ggd((n-1)(n+1),n+2)$
$=ggd(n-1,n+2)$ ($ggd(k,k+1)=1$)
$=ggd(3,n+2)$
$=1$ ($n \not\equiv 1 \pmod 3$).

Dat laatste is een contradictie met het gegeven, dus $n \equiv 1 \pmod 3$.

Lemma 5: $b \geq 6$.

Uit lemma $2$ volgt dat $b \geq 4$, want $P(a+2)$ kan anders geen priemfactor gemeenschappelijk hebben met een ander element uit de verzameling.

Stel $b=4$. Wegens lemma $2$ geldt dat dan noodzakelijk $P(a+2)$ een priemfactor gemeenschappelijk heeft met $P(a+4)$, en wegens lemma $3$ geldt dan dat $a+2 \equiv 2 \pmod 7 \Leftrightarrow a \equiv 0 \pmod 7$. Analoog moet gelden dat $P(a+3)$ een priemfactor gemeenschappelijk heeft met $P(a+1)$, zodat wegens lemma $3$ $a+1 \equiv 2 \pmod 7 \Leftrightarrow a \equiv 1 \pmod 7$. Contradictie!

Stel $b=5$. Wegens lemma $2$ moet $P(a+3)$ een priemfactor gemeenschappelijk hebben met $P(a+1)$ of $P(a+5)$. Veronderstel W.L.O.G. $P(a+5)$. (Het bewijs voor $P(a+1)$ verloopt analoog). Wegens lemma $3$ geldt dan dat $a+3 \equiv 2 \pmod 7 \Leftrightarrow a \equiv 6 \pmod 7$. Hieruit volgt dat $P(a+2)$ geen priemfactor gemeenschappelijk kan hebben met $P(a+4)$ wegens lemma $3$ (en de redenering voor $b=4$), en wegens lemma $2$ moet het dan een priemfactor gemeenschappelijk hebben met $P(a+5)$. Dan volgt uit lemma $4$ dat $a+2 \equiv 1 \pmod 3 \Leftrightarrow a \equiv 2 \pmod 3$.

Uit lemma $2$ en lemma $3$ volgt tevens dat $P(a+4)$ een priemfactor gemeenschappelijk moet hebben met $P(a+1)$. Maar dan moet wegens lemma $4$ $a+1 \equiv 1 \pmod 3 \Leftrightarrow a \equiv 0 \pmod 3$. Contradictie!

Lemma 6: $n \equiv 7 \pmod {19} \Rightarrow ggd(P(n), P(n+4)) >1$.

Bewijs: $P(n) \equiv 11+7+1 \equiv 0 \equiv 7+11+1 \equiv P(n+4) \pmod {19}$, zodat $ggd(P(n), P(n+4))\geq 19$.

Nu blijft nog over te bewijzen dat $b=6$ voldoet. We veronderstellen dat $P(a+1)$ en $P(a+4)$ een factor gemeen hebben, $P(a+3)$ en $P(a+5)$ een factor gemeen hebben en dat $a \equiv 5 \pmod {19}$. Uit lemma $6$ volgt dan dat $P(a+2)$ en $P(a+6)$ een factor gemeenschappelijk hebben. Uit resp. lemma $2$ en lemma $3$ volgt tevens dat $a \equiv 6 \pmod 7$ en $a \equiv 0 \pmod 3$. Er bestaat een $a$ die aan al deze voorwaarden voldoet wegens de Chinese reststelling.

Dus er bestaat een $a$ zodat de verzameling $\{P(a+1),P(a+2),P(a+3),P(a+4),P(a+5),P(a+6) \}$ welriekend is. Q.E.D.