makkelijker dan probleem 1

We zullen eerst volgend lemma bewijzen:

Lemma: voor elke priemfactor $p$ van $n$ geldt dat $v_p(n)=1$.

Bewijs: Allereerst moeten we opmerken dat noodzakelijk $n$ en $1$ een paar zullen vormen. Voor alle andere delers $q$ van $n$ geldt namelijk dat $q+n$ deelbaar is door $q$. Dus zal $n+1$ priem zijn. Beschouw nu $\frac{n}{p}$. Veronderstel dat deze gepaard wordt met deler $\alpha \neq 1$. Als $\alpha$ een deler $q$ heeft verschillend van $p$, dan zal $\alpha +\frac{n}{p}$ deelbaar zijn door $q$. Dus $\alpha$ is een macht van $p$. Maar als $v_p(n)>1$, zal $\frac np$ deelbaar zijn door $p$! dus dan is $\alpha+\frac np$ deelbaar door $p$, contradictie! Dus is $v_p(n)=1$ voor elke priemfactor van $n$.

Nu bewijzen we per volledige, omgekeerde inductie (d.w.z dat $S(q) \Rightarrow S(q-1)$ voor q, het aantal priemfactoren van deler $\alpha$) dat de deler die wordt gepaard met $\alpha$ gelijk is aan $\frac{n}{\alpha}$.

Inductiebegin: Stel dat $\alpha$ hetzelfde aantal priemfactoren als $n$ namelijk $q$ heeft. Dan zal $\alpha=n$ wegens het lemma, en deze wordt gepaard met $1=\frac nn$.

Inductiehypothese: Het geldt voor elke deler $\alpha$ met aantal priemfactoren $\ge k$.

Inductiestap: Stel dat $\alpha$, $k-1$ priemfactoren heeft. Stel $q$ het aantal priemfactoren van $n$. De deler $\beta$ waarmee $\alpha$ gepaard wordt heeft dan hoogstens $q-k+1$ priemfactoren. Stel namelijk dat deze er meer heeft, dan zal wegens het DVH $\alpha$ een priemfactor met $\beta$ gemeenschappelijk hebben: ze kunnen tesamen niet meer dan $q$ priemfactoren hebben. Stel nu dat $\beta$ strikt minder dan $q-k+1$ priemfactoren heeft, dus $\le q-k$. Er is echter een voor elke deler minder dan of gelijk aan $q-k$ priemfactoren een deler met groter dan of gelijk $k$ priemfactoren zodat deze twee delers geen priemfactoren gemeenschappelijk hebben (hun product is $n$). Deze worden gepaard wegens de inductiehypothese. Dus heeft $\beta$ exact $q-k+1$ priemfactoren. De enige deler met zoveel priemfactoren waarvoor $ggd(\alpha, \beta)=1$, is gelijk aan $\frac{n}{\alpha}$ wegens het lemma. Daarmee is de inductie afgesloten.

De priemgetallen gevormd door de paren van positieve delers van $n$ zijn dus telkens $\frac{n}{\alpha}+\alpha$, met $\alpha$ een positieve deler van $n$. Nu geldt voor elke priemfactor van $p_i$ van $n$ dat $p_i \mid \alpha$ of $p_i \mid \frac{n}{\alpha}$, maar niet allebei, wegens het lemma. Dus $n$ en $\alpha+\frac{n}{\alpha}$ hebben geen enkele priemfactor gemeenschappelijk. Hieruit volgt $ggd(n, \alpha+\frac{n}{\alpha})=1$. Omdat elke positieve deler minstens één is, is het onmogelijk dat $\alpha+\frac{n}{\alpha} \mid n$.

Stel nu dat $\alpha+\frac{n}{\alpha}=\beta+\frac{n}{\beta} \Leftrightarrow n( \frac{\beta-\alpha}{\alpha \beta})= \beta-\alpha \Leftrightarrow \alpha=\frac{n}{\beta} \text{of } \alpha=\beta$. Hieruit volgt dat deze priemgetallen de som zijn van dezelfde paren van delers. Q.E.D.