getaltheorie 6

Antwoord: exact alle oneven getallen.

Bewijs: Per volledige inductie. Eerst voeren we wat terminologie in. De hoofdstelling van de rekenkunde staat ons toe om te schrijven; $n=\prod_{i=1}^q p_i^{\alpha_i}$ met $p_1, ..., p_q$ allen verschillende priemgetallen en $\alpha_i \in \mathbb{N}\setminus \{0\}$. Dan is $\frac{\tau(n^2)}{\tau(n)}=\prod_{i=1}^q \frac{2\alpha_i+1}{\alpha_i+1}(=*)$. We zien dat zich in de teller enkel en alleen oneven getallen bevinden; vandaar kan $m$ enkel oneven zijn. Nu noemen we een lijst $(\alpha_1, \alpha_2, ..., \alpha_q)$, $m$-voldoende indien $*=m$ voor deze $\alpha_i$. De waarde van deze lijst is de uitkomst van $*$ hiervoor. Het is duidelijk dat er, indien zo'n lijst bestaat, ook een $n$ bestaat die voldoet. We noteren $[m]$ als een lijst die $m$-voldoende is, indien deze bestaat. We zullen deze soms in de lijst noteren, als volgt: $([m], \alpha_1, ..., \alpha_q)$. Dan wilt dit zeggen dat je moet aanvullen met de getallen uit een lijst die $m$-voldoende is. Dit komt neer op het vermenigvuldigen van het resultaat van $(\alpha_1, ..., \alpha_q)$ met $m$. Nu kunnen we beginnen.

Inductiebegin: Voor $m=1$ voldoet $n=1$. Voor $m=3$ voldoet de lijst $(2,4)$.

Inductiehypothese: Er bestaat een $m$-voldoende lijst voor alle oneven $1$<$m\le k-2$ ($k$ oneven).

Inductiestap: We noteren $k+1=2^{n} (2l+1)$. Er moet gelden dat $l \ge 0$ en $n\ge 1$ want $k$ is oneven. Laat nu $(a_y)_y$ gedefinieerd zijn als:

$a_0=(2^{n}-1)(2l+1)-1$
$a_{y+1}=2 a_y$.

Per inductie is het duidelijk dat de waarde van $(a_0, a_1, ..., a_x)$ gelijk is aan $\frac{a_{x+1}+1}{a_0+1}$, en ook dat $a_x=2^x a_0$. Dus is $a_{n}=2^{n} a_0=2^{n}(2^{n}-1)(2l+1)-2^{n}+1-1=(2^{n}-1)((2l+1)2^{n}-1)-1=(2^n-1)k-1$. Dan is $(a_0, ..., a_{n-1})$ gelijk aan $\frac{k}{2l+1}$. Nu is duidelijk $2l+1$<$k$ want $n \ge 1$ en $k>1$. Stel dat $l=0$, dan zijn we al klaar. Anders bestaat er wegens de inductiehypothese een $2l+1$-voldoende lijst. Dus $([2l+1],a_0, a_1, ..., a_{n-1})$ is een $k$-voldoende lijst. Q.E.D.