Zahlentheorie

1

Einleitung

Zahlentheorie, Zweig der Mathematik, der sich mit den Eigenschaften und Beziehungen von Zahlen beschäftigt.

Gemäß dieser breiten Definition gehört vieles der Mathematik zur Zahlentheorie. Im Allgemeinen beschränkt sie sich jedoch auf die Untersuchung der natürlichen und der ganzen Zahlen oder Zahlenmengen mit ähnlichen Eigenschaften. Der deutsche Mathematiker Carl Friedrich Gauß bezeichnete die Zahlentheorie als die „Königin der Mathematik”. Eine Eigentümlichkeit der Zahlentheorie besteht darin, dass viele ihrer Wahrheiten leicht durch Probieren entdeckt werden können, aber meist schwierig zu beweisen sind. „Gerade dieses ist es”, sagte Gauß, „was der höheren Arithmetik jenen zauberischen Reiz gibt, der sie zur Lieblingswissenschaft der ersten Geometer” (d. h. Mathematiker) „gemacht hat, ihres unerschöpflichen Reichtums nicht zu gedenken, woran sie alle anderen Teile der Mathematik so weit übertrifft.” Aber nicht nur Mathematiker hat der Reiz der Zahlentheorie erfasst: Zu allen Zeiten haben sich auch Laien mit den Eigenschaften der Zahlen beschäftigt und immer wieder neue Eigenschaften gefunden, Religionen haben ihre heiligen Zahlen und sogar mystische und magische Eigenschaften wurden (und werden) den Zahlen zugeschrieben. Heute hat die Zahlentheorie den Bereich der reinen Mathematik längst überschritten und ist z. B. ein wesentliches Hilfsmittel in der allgegenwärtigen Kryptologie unseres elektronischen Zeitalters geworden.

2

Teilbarkeit ganzer Zahlen

2.1

Die Teiler einer ganzen Zahl

Eine ganze Zahl b heißt Teiler der ganzen Zahl a, wenn die Division von a durch b „aufgeht”, d. h., wenn es eine ganze Zahl c gibt, so dass a = bc ist. Jede Zahl a besitzt die „trivialen” Teiler ±1 und ±a. Ist b von ±1 und ±a verschieden, so heißt b ein echter Teiler – z. B. ist 4 ein echter Teiler von 12, denn es ist 12 = 3 · 4. Dagegen ist 5 kein Teiler von 12. Ist b ein Teiler von a, so schreibt man b|a und nennt a ein Vielfaches von b. Dem rätselhaften Charakter unserer Zahlen begegnet man schon hier: Die Anzahl der Teiler einer Zahl ist kaum vorhersehbar, aufeinander folgende Zahlen können ganz verschiedene Teileranzahlen haben. Zum Beispiel hat 59 keine echten Teiler, während 60 sehr viele Teiler hat: 2, 3, 4, 5, 6, 10, 12, 15, 20, 30 (und ihre Negativen). 61 hat wieder nur die trivialen Teiler ±1 und ±61.

2.2

Gemeinsame Teiler zweier ganzer Zahlen

Teilt eine Zahl c die Zahlen a und b, so heißt c ein gemeinsamer Teiler von a und b. Um die gemeinsamen Teiler zweier Zahlen zu finden, genügt es den größten gemeinsamen Teiler zu finden, denn man kann zeigen, dass alle gemeinsamen Teiler den größten unter ihnen teilen. So hat beispielsweise die Zahl 18 die positiven Teiler 1, 2, 3, 6 und 9, also mit 60 die gemeinsamen positiven Teiler 1, 2, 3 und 6. Der größte gemeinsame Teiler von 18 und 60 ist daher 6, und alle anderen gemeinsamen Teiler teilen die 6. Den größten gemeinsamen Teiler von a und b bezeichnet man mit ggT(a,b). Zwei Zahlen heißen teilerfremd zueinander, wenn ihr größter gemeinsamer Teiler gleich 1 ist. Zum Beispiel sind aufeinander folgende Zahlen stets teilerfremd: 4 und 5, 36 und 37, aber auch 4 und 9 sind teilerfremd.

Analog zum größten gemeinsamen Teiler ist das kleinste gemeinsame Vielfache zweier Zahlen die kleinste natürliche Zahl, die von a und b geteilt wird; die Bezeichnung ist kgV(a,b). Das kleinste gemeinsame Vielfache benutzt man z. B., um Brüche auf einen möglichst kleinen gemeinsamen Nenner zu bringen (den so genannten Hauptnenner). Zwischen dem kleinsten gemeinsamen Vielfachen und dem größten gemeinsamen Teiler besteht die Beziehung

ggT(a,b) · kgV(a,b) = a · b.

Kennt man also den größten gemeinsamen Teiler zweier Zahlen, so ist auch das kleinste gemeinsame Vielfache bekannt.

2.3

Der euklidische Algorithmus

Der größte gemeinsame Teiler lässt sich auf sehr einfache und schnelle Weise berechnen. Das ist auch für die praktische Rechnung – heute also für die Computer – von Bedeutung: Ein Bruch a/b lässt sich dadurch vereinfachen, dass man den größten gemeinsamen Teiler wegkürzt, also zum „reduzierten Bruch” übergeht, z. B. 18/60 = 3/10. Da beim Rechnen mit Brüchen Zähler und Nenner sehr groß werden können, müssen die Brüche ständig wieder reduziert werden, um einen Overflow zu vermeiden. Das verwendete Verfahren ist der euklidische Algorithmus, der von Euklid in seinen Elementen beschrieben wurde, unter dem Namen „Wechselwegnahme” aber schon einige Jahrhunderte zuvor bekannt war. Die Idee der Wechselwegnahme ist ganz einfach: Gesucht ist der größte gemeinsame Teiler von a und b, wobei a größer als b sei. Wenn d der größte gemeinsame Teiler von a und b ist, teilt d auch die Differenz c = a - b. Diese Differenz ist aber kleiner als a. Der gesuchte Teiler d teilt also auch die kleineren Zahlen b und c. Fährt man auf diese Weise fort, indem man immer die kleinere Zahl von der größeren abzieht (das ist die „Wechselwegnahme”), so gelangt man zu immer kleineren Zahlen und schließlich zu einer Zahl, welche die vorherige teilt. Dies ist der gesuchte größte gemeinsame Teiler von a und b.

Hierzu ein Beispiel: Gesucht ist der größte gemeinsame Teiler von 56 und 35. Die Wechselwegnahme ergibt:

• 56 - 35 = 21,
• 35 - 21 = 14,
• 21 - 14 = 7, und 7 teilt 14.

Also ist 7 der größte gemeinsame Teiler von 56 und 35.

Man kann dieses Verfahren den Urvater aller Algorithmen nennen, denn es ist der erste wirkliche Algorithmus in der Geschichte der Mathematik (und meist der erste Algorithmus, den man beim Programmieren ausprobiert), und obwohl er nun schon Jahrtausende alt ist, wird er in verfeinerter Form in jedem Rechner installiert sein.