Problem 1713

Solution:

Noem $b_{i}=a_{1} a_{2} \cdots a_{i}$, voor $1 \leq i \leq p$. We bewijzen dat het mogelijk is de permutatie zo te kiezen dat $b_{i} \equiv i \bmod p$ voor alle $i$. Voor $i \geq 2$ is $a_{i} \equiv b_{i} \cdot b_{i-1}^{-1} \bmod p$ als $b_{i-1} \not \equiv 0 \bmod p$. We kiezen nu dus $a_{1}=1$ en $a_{i} \equiv i \cdot(i-1)^{-1} \bmod p$ voor $2 \leq i \leq p$. Het is nu voldoende te bewijzen dat $a_{i} \not \equiv 1 \bmod p$ voor alle $2 \leq i \leq p$ en $a_{i} \not \equiv a_{j} \bmod p$ voor alle $2 \leq j<i \leq p$.

Stel uit het ongerijmde dat $a_{i} \equiv 1 \bmod p$ voor zekere $2 \leq i \leq p$. Dan is $i \cdot(i-1)^{-1} \equiv 1$ $\bmod p$, dus $i \equiv i-1 \bmod p$, dus $0 \equiv-1 \bmod p$. Omdat $p \geq 2$ is dit een tegenspraak. Stel nu dat $a_{i} \equiv a_{j} \bmod p$ voor zekere $2 \leq j<i \leq p$. Dan geldt $i \cdot(i-1)^{-1} \equiv j \cdot(j-1)^{-1}$ $\bmod p$ dus $i(j-1) \equiv j(i-1) \bmod p$ dus $i j-i \equiv i j-j \bmod p$ dus $-i \equiv-j \bmod p$. Maar we hadden $2 \leq j<i \leq p$, dus dit kan niet.

We concluderen dat als we de $a_{i}$ kiezen zoals hierboven aangegeven, alle $a_{i}$ verschillend worden, zodat het inderdaad een permutatie van $1,2, \ldots, p$ is. Verder geldt nu per definitie dat $a_{1} a_{2} \cdots a_{i} \equiv i \bmod p$, zodat ook aan de tweede eis is voldaan.