korte (?) priem rij
Opgave - RMM 2013 dag 1 vraag 1
Zij $a$ een strikt natuurlijk getal, definieer een rij getallen$ x_1, x_2,\cdots$ via
$x_1 = a$ and $x_{n+1} = 2x_n+1$ $\forall n \ge 1$. Laat $y_n = 2^{x_n}-1$ zijn. Vind de grootst mogelijke waarde voor $k$ zodat voor een bepaalde $a$ : $y_1,y_2 \cdots y_k$ allen priem zijn.
- login om te reageren
Oplossing
We zullen bewijzen dat $k \leq 2$. Hiervoor tonen we eerst volgend lemma aan:
Lemma: Als voor een priemgetal $p$: $2p+1 \equiv \pm 1 \pmod 8$ en priem is, dan zal $2p+1 \mid 2^p-1$. Als $p>3$ zal $2^p-1$ tevens samengesteld zijn.
Bewijs: Er geldt dat $\left ( \frac{2}{2p+1} \right)=1$ aangezien $2p+1 \equiv \pm 1 \pmod 8$. Hierom geldt dat, wegens de congruentie van Euler, $2^p\equiv 1 \pmod {2p+1}$. Dus $2p+1 \mid 2^p-1$.
Als nu geldt dat $2^p-1$ priem is, moet noodzakelijk $2p+1=2^p-1$, dus $p+1=2^{p-1}$. Via inductie is het zeer makkelijk aan te tonen dat $p>3 \Rightarrow 2^{p-1}>p+1$. Voor $p=3$ treedt er gelijkheid op en voor $p<3$ geldt de ongelijkheid in omgekeerde zin. Hiermee is het lemma bewezen.
Merk nu op dat, als een bepaalde $x_i$ niet priem is, $y_i$ ook niet priem is. Dit volgt uit het feit dat $2^a-1 \mid 2^{ab}-1$ en $2^1-1=1$. Dus moet voor alle $1 \leq i \leq k$: $x_i$ priem zijn. In het bijzonder is $a$ priem.
Veronderstel dat $a>3$. Dan is $a$ oneven. Wegens het lemma geldt dat als $x_2 \equiv \pm 1 \pmod 8$, dat $y_1$ dan niet priem is. Bijgevolg is $a$ congruent met $1$ of $5$ modulo $8$. Stel $a\equiv 1 \pmod 8$. Dan zal $x_3=4a+3 \equiv -1 \pmod 8$. Dus zal wegens het lemma $y_2$ niet priem zijn. Stel $a\equiv 5 \pmod 8$. Ook dan zal $x_3 \equiv -1 \pmod 8$. Dus ook nu is $y_2$ niet priem.
Laat nu $a=3$. Dan zal $y_1=7$, $y_2=127$ en $y_3=2^{15}-1$, dus is $y_3$ niet priem.
Laat nu $a=2$. Dan zal $y_1=3$, $y_2=31$ en $y_3=2^{11}-1=23 \cdot 89$. Dus ook nu is $y_3$ niet priem.
Hieruit volgt dat $k \leq 2$. Q.E.D.