Beobachtungen, die beim Teilen natürlicher Zahlen durch andere natürliche Zahlen (außer 1) gemacht werden, führen zu Aussagen, die der mathematischen Disziplin ‚Elementare Zahlentheorie‘ angehören. Insbesondere betreffen solche Aussagen Faktorenzerlegungen, Teilbarkeitsregeln und Divisionsreste. Ein zentraler Begriff in der elementaren Zahlentheorie ist der Begriff der Primzahl.
Beispiele für Primzahlen, Faktorenzerlegungen und Divisionsreste liefert heute jedes Computer-Algebra-System (CAS). Die meisten CAS verstehen die Befehle NEXT_PRIME(n) zum Aufrufen der nächsthöheren Primzahl oberhalb einer gegebenen Zahl n, FACTOR(z) zum Aufrufen der Primfaktorenzerlegung einer Zahl z und MOD(a, b) zur Bestimmung des Divisionsrestes bei Division von a durch b.
Eine Primzahl ist eine natürliche Zahl mit genau zwei verschiedenen natürlichen Teilern. Der Befehl FACTOR(71) wird von CAS mit 71 beantwortet. 71 ist also eine Primzahl. Ein Verfahren zur einfachen Bestimmung von Primzahlen unter einer Schranke s hat der griechische Mathematiker Eratostenes bereits im 3. Jahrhundert v.Chr. beschrieben. Näheres findet man im Internet. Den Befehl FACTOR(91) beantwortet CAS mit 7ˑ13. Die Zahl 91 heißt auch zusammengesetzte Zahl.
Ein historisch interessantes Beispiel für eine Faktorenzerlegung ist folgendes: $$2^{67}-1 = 147573952589676412927=193707721 \cdot 761838257287$$Ein Computer-Algebra-System (CAS) berechnet heute diese Zeile in weniger als einer Sekunde. Im Jahre 1903 erntete ein gewisser Nelson Cole stehenden Applaus von der ‚American Mathematical Society‘ für diese Rechnung. Bis zum Jahre 1876 galt nämlich die Behauptung des Minoritenbruders Marin Mersenne: „\(2^{67}-1\) ist eine Primzahl“. Im Jahre 1876 hatte dann der französische Mathematiker Edouard Lucas beweisen können, dass \(2^{67}-1\) das Produkt zweier von 1 verschiedener Zahlen ist, ohne diese Zahlen nennen zu können.
Cole soll später gestanden haben, für seine Rechnung die Sonntage von 3 Jahren geopfert zu haben. Prinzipiell hat sich an der Situation Coles auch nach der Erfindung digitaler Rechenmaschinen nicht viel geändert außer, dass es wesentlich größerer Zahlen bedarf, um deren Faktoren mit einem digitalen Werkzeug erst nach über 150 Tagen Rechenzeit zu finden. Das Problem der Faktorenzerlegung ist der Mathematik erhalten geblieben. Genau dieses Problem macht sich das RSA-Verschlüsselungsverfahren zunutze.
Vor der Einführung digitaler Werkzeuge in den Mathematikunterricht waren sogenannte Teilbarkeitsregeln (Endstellenregeln für 2, 4 und 5; Quersummenregeln für (3, 7, 9 und 11) Unterrichtsthema in der 6. Klasse. Das erscheint heute unnötig, da Computer die Zerlegung von natürlichen Zahlen in natürliche Faktoren in der Größenordnung, wie sie in der Schule vorkommen, in Bruchteilen von Sekunden liefern. Aus rein mathematischer Sicht bleibt allerdings die Frage interessant: Was steckt hinter einer Regel, welche hilfsmittelfrei die Teilbarkeit durch 3 oder 9 in Sekunden prüft? Warum gilt diese Teilbarkeitsregel? Wer angesichts digitaler Werkzeuge solche Fragestellungen für unnütz hält, den kann sowohl die elementare Zahlentheorie als auch die Mathematik im allgemeinen nicht wirklich interessieren.
