Jantje zag eens pruimen hangen

Voor het oplossen van de vraag bewijzen we eerst de volgende stelling: " Als $p$ een priemgetal is, dan is $p^{2k+1}$ (met $k\in \mathbb{N}$) een pruimgetal."

Het is duidelijk dat elk priemgetal $p$ een pruimgetal is aangezien 1 geen pruimgetal is en een priemgetal buiten 1 en zichzelf geen andere delers heeft. We bewijzen nu door middel van sterke inductie dat $p^{2k+1}$ een pruimgetal is. Voor $k=0$ hebben we gezien dat de stelling klopt. Veronderstel nu dat de stelling klopt voor $0 \leq n \leq k$ met $n \in \mathbb{N}$, we bewijzen de stelling voor $k+1$ :

$p^{2(k+1)+1}=p^{2n+1}\cdot p^{2(k-n)}$

Omdat de exponent oneven is, is de ontbinding van $p^{2k+1}$ ook altijd in factoren met een even en een oneven exponent van $p$ (een oneven getal is altijd de som van een even en een oneven getal). Omdat we verondersteld hebben dat $p^{2n+1}$ voor $0 \leq n \leq k$ altijd pruim is moet $p^{2(n+1)}=p \cdot p^{2n+1}$ niet pruim zijn (product van twee pruimgetallen). Maar $n$ is willekeurig tussen 0 en $k$, dus elke macht van $p$ met even exponent kleiner dan $k$ is geen pruimgetal, bijgevolg is $p^{2(k-n)}$ dus geen pruimgetal. We concluderen dat $p^{2(k+1)+1}$ niet te schrijven is als het product van twee pruimgetallen en dus geldt de stelling voor $k+1$, en hebben we hierbij bewezen dat elke oneven macht van een priemgetal een pruimgetal is.

We zien nu dat $100 000=2^{5}\cdot 5^{5}$ en omdat 2 en 5 priemgetallen zijn weten we dat $2^5$ en $5^5$ pruimgetallen zijn, en dus voldoet $100 000$ niet aan de definitie van een pruimgetal.