rekenkundige rij

Het is duidelijk dat $(a_i)_k$ een strikt stijgende rij is. Het is dus ook een unieke rij, want $a_1$ moet dus het kleinste element zijn en $a_2$ het tweede kleinste etc. Merk ook op dat $k = \phi(n)$, met $\phi$ de euler-totient functie.

Het is duidelijk dat als $n$ priem of $n$ een macht van $2$ is, de statement inderdaad waar is (als $n$ priem is heb je $a_i - a_{i-1} = 1$ voor alle $2 \le i \le {p-1}$ met $a_1 = 1$, als $n$ een macht van twee is heb je $a_i - a_{i-1} = 2$ voor alle $2 \le i \le \frac{p}{2}$ met $a_1 = 1$).

Stel nu dat het kleinste priemgetal waar $n$ onderling mee ondeelbaar $q$ is en dus $a_2 = q$. Als $q=2$, moet $a_2 - a_1 = 1$, en vind je per inductie dat $a_i = i$, wat wil zeggen dat $n$ priem moet zijn. Dit geval hebben we al gehad dus beschouw $q \neq 2$.

Dus stel nu dat $a_2 = q$. Hierdoor is $a_3 = 2q-1$. Merk op dat $a_{\phi(n)} = n-1$, want $ggd(n,n-1) = 1$ uiteraard. Nu is $a_n = 1 + (n-1)(q-1)$, dus willen we dat, door $n$ te vervangen door $\phi(n)$: $a_{\phi(n)} = n-1 = 1 + (\phi(n)-1)(q-1)$. Dus $q-1|n-2$.

Stel dat $q$ niet van de vorm $2^x+1$ is en dat er een oneven priemgetal $p$ bestaat met $p|q-1$. Nu moet $p|n-2$ en moet $p|n$ want $q$ is het kleinste priemgetal onderling ondeelbaar met $n$ dus moet $p$ een deler van $n$ zijn. Nu is $p|n-2$ en $p|n$ of $p|2$, maar $p$ was een oneven priemgetal, tegenspraak.

Bijgevolg is $q$ van de vorm $2^x+1$.

Geval 1: $q=3$. Hierdoor is $n$ automatisch een tweedemacht want per inductie vind je dat $a_i = 2i-1$ m.a.w. $2$ is het enige priemgetal dat $n$ deelt.

Geval 2: $q>3$. Nu $a_2 = q \neq 3$, wil dit zeggen dat $3|n$. Aangezien $q = 2^x+1$ moet $x$ even zijn, want stel dat $x$ oneven is: we krijgen door $\pmod{3}$ te kijken dat $3|q$, tegenspraak met het feit dat $q$ priem is.

Nu is $a_3 = 2q-1 \equiv 0 \pmod{3}$, maar $2q-1$ moet onderling ondeelbaar met $n$ zijn terwijl $3|n$ en $3|2q-1$, dus $ggd(n,2q-1) = 3$, tegenspraak.