| 1. Schritt: | Euklid nimmt an, daß es nur endlich viele Primzahlen gibt. |
| 2. Schritt: | Wenn es nur endlich viele gibt, dann kann man diese durchnumerieren und nach Größe sortieren. Die Menge der Primzahlen ist dann P=[2,3,5,7,11,13,....pn] |
| 3. Schritt: | Euklid bildet das Produkt aller dieser Primzahlen und addiert 1 hinzu: q=2*3*5*7*11*13*...*pn+1 |
| 4. Schritt: | q besitzt nun Teiler aus P, da P alle Primzahlen enthält. |
| 5. Schritt: | Durch welche Primzahl aus P man q aber teilt, es bleibt immer der Rest 1. |
| 6. Schritt: | Keine Primzahl aus P kann ein Teiler von q sein, q hat also einen anderen Primteiler oder ist selbst eine Primzahl. |
| 7. Schritt: | Schritt 6 ist ein Widerspruch zur Annahme, daß in P schon alle Primzahlen sind. Die Annahme, daß es nur endlich viele Primzahlen gibt, ist somit falsch. |
| 8. Schritt: | Es gibt also unendlich viele Primzahlen! |
Der erste Schritt zur Kryptographie, der Beweis für die unendliche Menge der Primzahlen, ist nun gemacht. Für kurze Zeit werden wir mit diesem genial einfachen Beweis, der die Unendlichkeit der völlig unregelmäßig verteilten Primzahlen faßbar macht, die Primzahlen verlassen und uns einer weiteren "Erfindung" von Gauss zuwenden: den Kongruenzen.
zurück 