samengestelde getallen

Lemma 1: $d_2|d_i$ (voor alle $i \in \{2,...,k\}$)
Om dit Lemma te bewijzen, zullen we volledige inductie toepassen.

Inductiehypothese: $d_2|d_i$ voor alle $2 \le i \le \ell$.

1) Basis
Er geldt uiteraard: $d_2|d_2$.
Nu zullen we bewijzen dat ook $d_2|d_3$.
Wegens het gegevene geldt dat $d_{k-2}|d_{k-1}+d_k$. Omdat $d_k=n$ en omdat $d_{k-2}|n$, geldt ook dat $d_{k-2}|d_k$ (merk op dqt $k \ge 3$). Daarom geldt dat $d_{k-2}|d_{k-1}$. Wegens de definitie van deelbaarheid geldt: $\exists q \in \mathbb{N} \colon d_{k-1}=q \cdot d_{k-2}$. $(1)$

Daar $1=d_1< d_2 < ... < d_k=n$ de delers zijn van $n$ in volgorde, geldt $d_i d_{k+1-i}=n$ voor elke $1 \le i \le k,$
en dus in het bijzonder $d_{k-2}=\frac{n}{d_3}$ en $d_{k-1}=\frac{n}{d_2}$.
$\frac{n}{d_2}=q \cdot \frac{n}{d_3}$
$\Longrightarrow d_{3}=q \cdot d_{2}$
$\Longrightarrow d_2|d_3$ (definitie van deelbaarheid).
De industiehypothese is dus waar voor $\ell=3$.

2) Inductiestap
De Inductiehypothese zegt dat $d_2|d_{l-1}$ en $d_2|d_l$ (met $3 \leq l \leq k-1$).
Wegens het gegevene geldt dat $d_{l-1}|d_l+d_{l+1}$.
Omdat $d_2|d_{l-1}$ (wegens de Inductiehypothese), geldt ook dat: $d_2|d_l+d_{l+1}$.
Omdat $d_2|d_l$ (wegens de Inductiehypothese), geldt ook dat: $d_2|d_{l+1}$.
Hiermee is de inductiestap bewezen, en volgt het lemma wegens volledige inductie.

Hoofdbewijs
We zullen aantonen dat de enige samengestelde getallen, die voldoen, van de vorm $n=p^t$ zijn, met $p$ een priemgetal, en $t \in \mathbb{N} \backslash \{0,1\}$. Veronderstel dus, ter wille van de contradictie, dat $n$ twee of meer verschillende priemfactoren in zijn priemfactorontbinding heeft.
Neem de kleinste priemfactor $p_1$, en neem ook een willekeurige andere priemfactor $p_2$. Aangezien priemfactoren ook delers zijn, en $p_1$ de kleinste priemfactor is, is $p_1=d_2$ en $p_2=d_x$ voor een bepaalde $x>2$ en $x < k$.
Wegens Lemma $1$ geldt dan: $d_2|d_x$ en dus ook $p_1|p_2$. Maar $p_2$ is een priemgetal, en verschillend van $p_1$, zodat we een contradictie bekomen. We kunnen dus besluiten dat onze assumptie fout was, zodat $n$ juist $1$ verschillende priemfactor heeft, en $n$ dus van de vorm $n=p^t$ moet zijn.

Nu rest ons nog aan te tonen dat deze getallen wel degelijk voldoen. Welnu, $d_j=p^{j-1}$ (met $j \in \{1,...,t+1\})$, zodat $d_{i+1}+d_{i+2}=p^{i}+p^{i+1}=p^{i-1}(p+p^2)=(p+p^2) \cdot d_i$.
Er geldt dus inderdaad dat $d_i|d_{i+1}+d_{i+2}$.
We kunnen dus besluiten dat het gevraagde geldt als en slechts als $n$ van de vorm $n=p^t$ (met $p$ een priemgetal, en $t \in \mathbb{N} \backslash \{0,1\}$) is.