getaltheorie 3

We bewijzen dat zo'n $n$ voor elke $k$ verschillende priemfactoren bestaat, dus ook $2000$, per inductie. In het bijzonder tonen we aan dat er steeds zo'n $n$ bestaat met $v_3(n)=k.$

Inductiebegin: Zij $k=1$. We zien dat $n=3$ werkt; immers $3 \mid 2^3+1=9$. Verder is $v_3(n)=1$.

Inductiehypothese: Veronderstel dat het geldt voor $k$.

Inductiestap: Zij $n$ dat getal voor $k$. We bewijzen eerst volgend lemma:

Lemma: Voor alle $b>2$ heeft $b^3+1$ een priemfactor die $b+1$ niet heeft.

Bewijs: Dit volgt natuurlijk rechtstreeks uit Zsigmondy, maar het is ook makkelijk te bewijzen zonder. We zien namelijk dat $ggd(\frac{b^3+1}{b+1}, b+1)=ggd(b^2-b+1, b+1)=ggd(2b-1, b+1)=ggd(3, b+1) \mid 3$. Omdat $b>2$, zien we dat $b^2-b+1>3$ zodat $b^2-b+1$ zeker een priemdeler heeft die $b+1$ niet heeft, m.a.w. $b^3+1$ heeft een priemfactor die $b+1$ niet heeft, waarmee het lemma bewezen is.

Uit het lemma volgt dat $2^{3 n}+1$ een priemfactor heeft die $2^n+1$ niet heeft (we weten dat $b=2^n>2$ omdat $n \ge 3$). Zij $p$ die priemfactor, dan voldoet $q=3pn$. Inderdaad, we zien dat $p \mid 2^{3n}+1\mid 2^q+1$, $n \mid 2^n+1 \mid 2^q+1$. Verder is $v_3(q)=k+1$ en omdat $n$ oneven is ($2^n+1$ bevat geen factoren twee), hebben we dat $v_3(2^q+1)=v_3(2+1)+v_3(q)=k+2>v_3(q)$ wegens LTE, dus ook $3^{k+1} \mid 2^q+1$. Merk nu op dat $q=kgv(p, n, 3^{k+1})$, omdat $p$ geen deler is van $2^n+1$ en dus ook niet van $n$. Dus $q \mid 2^q+1$ en heeft $k+1$ priemdelers. Q.E.D.