54 2 ZAHLEN UND ZAHLENMENGEN 2.6 Teilbarkeit und Primzahlen Teiler einer natürlichen Zahl Da 3 · 4 = 12 ist, lautet die Division 12 : 3 = 4 mit 0 Rest, und man sagt: „3 ist ein Teiler von 12.“ Analog erhält man: „4 ist ein Teiler von 12.“ Allgemein: Definition Es seien a, b * N*. Man sagt: a ist Teiler von b, wenn es ein x * N* gibt, sodass a · x = b. Man schreibt: a ! b [Lies: a ist Teiler von b. Oder: a teilt b] a ~ b [Lies: a ist kein Teiler von b. Oder: a teilt nicht b] Primzahlen L Jede natürliche Zahl n * N* besitzt die Teiler 1 und n. Manche natürliche Zahlen besitzen keine anderen Teiler. Definition • Eine natürliche Zahl p > 1 heißt Primzahl, wenn sie außer 1 und p keinen Teiler besitzt. • Eine natürliche Zahl n > 1, die keine Primzahl ist, heißt zusammengesetzte Zahl. BEISPIEL Die gerade Zahl 2 244 besitzt den Teiler 2, ist also keine Primzahl, sondern eine zusammengesetzte Zahl. Sie kann vollständig in Primfaktoren zerlegt werden: 2 244 = 2 · 1 122 = 2 · 2 · 561 = 2 · 2 · 3 · 187 = 2 · 2 · 3 · 11 · 17 Das Produkt 2 · 2 · 3 · 11 · 17 nennt man die Primfaktorenzerlegung von 2 244. Fundamentalsatz der Zahlentheorie (1) Jede zusammengesetzte natürliche Zahl n > 1 lässt sich als Produkt von Primzahlen darstellen. (2) Diese Darstellung ist eindeutig bis auf die Reihenfolge der Primfaktoren. BEWEIS- SKIZZE Es sei n eine zusammengesetzte Zahl. Da n keine Primzahl ist, besitzt n neben 1 und n noch mindestens einen weiteren Teiler und lässt sich somit in ein Produkt zweier kleinerer natürlicher Zahlen a und b zerlegen. Falls eine dieser beiden Zahlen keine Primzahl ist, lässt sie sich auf die gleiche Weise weiter zerlegen. Auf diese Weise kann man mit dem Zerlegen fortfahren. Da die neu auftretenden Faktoren dabei immer kleiner sind als die vorhergehenden Zahlen, muss das Verfahren nach endlich vielen Schritten abbrechen, dh. es müssen schließlich alle auftretenden Faktoren Primzahlen sein. Die Eindeutigkeit der Darstellung bis auf die Reihenfolge der Primfaktoren ist intuitiv einsichtig. Einen genaueren Beweis führen wir jedoch nicht durch. BEMERKUNG D ie Zahl 1 wird nicht zu den Primzahlen gerechnet, weil sonst die Primfaktorenzerlegung nicht eindeutig wäre. ZB: 6 = 2 · 3 = 1 · 2 · 3 = 1 · 1 · 2 · 3 = 1 · 1 · 1 · 2 · 3 = … Satz Es gibt unendlich viele Primzahlen. L 2 244 2 1 122 2 561 3 187 11 17 17 1 kompakt S. 55 Nur zu Prüfzwecken – Eigentum des Verlags öbv
RkJQdWJsaXNoZXIy ODE3MDE=