MR 06 Loesung

Einfache Primzahl

zurück zur Aufgabenstellung

Zuerst werden alle Muster ausgeschlossen, die keine Primzahl sein können.

Ausgeschossen werden können erstens alle Ziffern 2 bis 9, da diese Zahl, bestehend aus lauter Ziffern z immer durch die Zahl z teilbar ist. D.h. 7777777...7777 ist durch 7 teilbar und darum keine Primzahl.

Betrachtet müssen nur mehr Zahlen, die aus lauter 1er bestehen. Die erste Zahl aus mehreren 1ern wäre 11. Die Zahl 11 wäre eine Primzahl. 11 wird aber lt. Aufgabenstellung ausgeschlossen, da nach Zahlen mit mehr als zwei Stellen gefragt wird.

Um weitere Muster ausschließen zu können, muss 1111...1111 - also n 1er ein wenig umgeschrieben werden:

$10^{n}-1$ ist eine Zahl, die aus n 9ern besteht.

${10^{n}-1} \over 9$ ist eine Zahl, die aus n 1ern besteht.

Ich betrachte jetzt nur gerade n. D.h. $n=2k$.

$10^{2k}-1=(10^{k}+1)(10^{k}-1)$

${{10^{2k}-1} \over 9}={{(10^{k}+1)(10^{k}-1)} \over 9}$

Da ja, wie weiter oben argumentiert $10^{k}-1$ durch 9 teilbar ist, gilt:

${{10^{2k}-1} \over 9}=(10^{k}+1){{(10^{k}-1)} \over 9}$

Somit ist die Zahl, bestehend aus 2 k 1ern durch $10^{k}+1$ teilbar.

Man muss also nur mehr die Zahlen, bestehend aus einer ungeraden Anzahl von 1ern betrachten.

Weil die Zahl, bestehend aus n 1ern die Ziffernsumme n hat, ist demnach jede solche Zahl, bei der n ein Vielfaches von 3 ist durch 3 teilbar. Die n, die Vielfache von 3 sind scheiden demnach auch aus.

Übrig bleiben (vorerst) alle n die nicht durch 2 und nicht durch 3 teilbar sind. Diese fange ich jetzt an in ihre Primfaktoren zu zerlegen. Dazu braucht man einen Rechner, der mit (dann) derart großen Zahlen umgehen kann. Heutzutage sind in normalen Haushalten vorhandene Rechner durchaus dazu in der Lage. Der free42 hat die folgende Tabelle gerechnet. An dem n=17 hat er/sie/es ca. 3 Minuten gerechnet. Für das letzte n=19 hat er/sie/es immerhin 3 Stunden gerechnet.

n	Zahl	Primfaktoren
5	11 111	= 41 \dot 271
7	1 111 111	= 239 \dot 4 649