Kurs:Grundkurs Mathematik (Osnabrück 2016-2017)/Teil I/Vorlesung 12

Aus Wikiversity
Wechseln zu: Navigation, Suche
„Man muss auch teilen können.“



Teilbarkeitseigenschaften

Wir besprechen nun die Eigenschaft, dass eine natürliche Zahl eine weitere natürliche Zahl teilt.


Definition  

Man sagt, dass die natürliche Zahl die natürliche Zahl teilt (oder dass von geteilt wird, oder dass ein Vielfaches von ist), wenn es eine natürliche Zahl derart gibt, dass ist. Man schreibt dafür auch .

Beispielsweise sind Teiler von und die Teiler von . Eine Zerlegung

nennt man auch eine Faktorzerlegung von . Wenn ein Teiler von ist und

so ist die Zahl mit nach der Kürzungsregel eindeutig bestimmt. Man nennt diese Zahl den Gegenteiler oder komplementären Teiler und schreibt dafür . Da wir im Moment die rationalen Zahlen noch nicht zur Verfügung haben, ist dies nur dann eine erlaubte Schreibweise, wenn die Teilerbeziehung vorliegt und ist (so wie die Schreibweise bisher nur erlaubt ist, wenn ist). Es ist also ein Teiler der , der Ausdruck ist aber nicht definiert.



Lemma  

Es sei eine natürliche Zahl und ein Teiler von .

Dann ist .

Insbesondere besitzt nur endlich viele Teiler.

Beweis  

Da der Teiler ausgeschlossen ist, sind bei einer Faktorzerlegung beide Faktoren . Wegen Satz 10.5  (3) ist daher

Der Zusatz ist klar, da es unterhalb von überhaupt nur endlich viele natürliche Zahlen gibt.


Wenn man also alle Teiler einer natürlichen Zahl finden möchte, so muss man einfach die Zahlen

der Reihe nach durchgehen und ihre Vielfachen

durchgehen, bis die Zahl auftaucht (in welchem Fall ein Teiler ist) oder eine Zahl auftaucht (dann liegt kein Teiler vor). Übrigens muss man nicht die Zahlen bis durchprobieren, sondern lediglich bis zur ersten Zahl mit (man muss also nur bis zur Größenordnung der Quadratwurzel aus gehen). Dann muss man aber für jeden Teiler

auch den Gegenteiler mitanführen, siehe Aufgabe 12.7. Für muss man maximal bis gehen. Es ergeben sich die Zerlegungen

und die Teiler sind somit .

Eine durch teilbare Zahl, also ein Vielfaches von , heißt gerade, eine nicht durch teilbare Zahl heißt ungerade. Für einige Zahlen gibt es einfache Tests, ob sie ein Teiler einer gewissen Zahl sind, die allerdings auf dem Dezimalsystem beruhen. Eine weitere wichtige Möglichkeit ist die Division mit Rest. Auch der dritte Teil des folgenden Lemmas hilft: Wenn kein Teiler von ist, so sind sämtliche Vielfache von ebenfalls kein Teiler von .



Lemma  

In gelten folgende Teilbarkeitsbeziehungen.

  1. Für jede natürliche Zahl gilt und .
  2. Für jede natürliche Zahl gilt .
  3. Gilt und , so gilt auch .
  4. Gilt und , so gilt auch .
  5. Gilt , so gilt auch für jede natürliche Zahl .
  6. Gilt und , so gilt auch für beliebige natürliche Zahlen .

Beweis  

  1. Ist klar wegen
  2. Ist klar wegen
  3. Die beiden Voraussetzungen bedeuten die Existenz von mit und . Somit ist

    und ist auch ein Teiler von .

  4. Aus den Voraussetzungen und ergibt sich direkt

    also ist ein Teiler von .

  5. Aus der Voraussetzung ergibt sich direkt

    also ist ein Teiler von .

  6. Aus den Voraussetzungen und ergibt sich direkt mit dem Distributivgesetz

    also ist ein Teiler von .


Verband Teiler30.png

Beispiel  

Wir betrachten die positiven natürlichen Zahlen zusammen mit der Teilbarkeitsbeziehung. Dies ergibt eine Ordnung auf . Die Teilbarkeitsrelation ist in der Tat reflexiv, da stets ist, wie zeigt. Die Transitivität wurde in Lemma 12.3  (3) gezeigt. Die Antisymmetrie folgt so: Aus und folgt . Da wir uns auf positive natürliche Zahlen beschränken, folgt mit der Kürzungsregel und daraus wegen auch . Also ist . Einfache Beispiele wie und zeigen, dass hier keine totale Ordnung vorliegt, da weder von noch umgekehrt geteilt wird.




Größter gemeinsamer Teiler und kleinstes gemeinsames Vielfaches

Definition  

Seien natürliche Zahlen. Dann heißt eine natürliche Zahl gemeinsamer Teiler der , wenn jedes teilt für .

Eine natürliche Zahl heißt größter gemeinsamer Teiler der , wenn ein gemeinsamer Teiler ist und wenn unter allen gemeinsamen Teilern der der (bezüglich der Ordnungsrelation auf den natürlichen Zahlen) Größte ist.

Beispielsweise haben die Zahlen die gemeinsamen Teiler , und ist der größte gemeinsame Teiler.


Definition  

Zwei natürliche Zahlen heißen teilerfremd, wenn sie keinen gemeinsamen Teiler besitzen.

Beispielsweise sind und teilerfremd, und sind nicht teilerfremd, da ein gemeinsamer Teiler ist. Die ist zu jeder natürlichen Zahl (auch zu und ) teilerfremd.


Definition  

Zu einer Menge von natürlichen Zahlen

heißt eine natürliche Zahl ein gemeinsames Vielfaches, wenn ein Vielfaches von jedem ist, also von jedem geteilt wird.

Die Zahl heißt das kleinste gemeinsame Vielfache der , wenn ein gemeinsames Vielfaches ist und unter allen gemeinsamen Vielfachen der , das Kleinste ist.

Die Existenz eines größten gemeinsamen Teilers ist wegen Lemma 12.2 klar. Die Existenz des kleinsten gemeinsamen Vielfachen ist ebenfalls klar, da das Produkt der Zahlen ein gemeinsames Vielfaches ist. Wir werden später als eine Anwendung der eindeutigen Primfaktorzerlegung (Satz 20.8) sehen, dass jeder gemeinsame Teiler den größten gemeinsamen Teiler teilt und dass jedes gemeinsame Vielfache ein Vielfaches des kleinsten gemeinsamen Vielfachen ist.



Primzahlen
Das Sieb des Eratosthenes liefert eine einfache Methode, eine Liste von Primzahlen unterhalb einer bestimmten Größe zu erstellen. Man streicht einfach die echten Vielfachen der kleinen (kleiner als oder gleich ) schon etablierten Primzahlen durch, die verbleibenden Zahlen sind prim.

Definition  

Eine natürliche Zahl heißt eine Primzahl, wenn die einzigen natürlichen Teiler von ihr und sind.

Eine Primzahl ist also eine natürliche Zahl, die genau zwei Teiler hat, nämlich und , und die müssen verschieden sein. ist also keine Primzahl.

Die ersten Primzahlen sind . Für eine Primzahl und eine natürliche Zahl gilt folgende Alternative: Entweder teilt die Zahl , oder aber und sind teilerfremd. Ein gemeinsamer Teiler muss ja ein Teiler von sein, und da kommen nur und in Frage.

Ein wichtiger Satz ist der Satz über die eindeutige Primfaktorzerlegung. Eine einfache Version davon ist der folgende Satz.



Satz  

Jede natürliche Zahl , , besitzt eine Zerlegung in Primfaktoren.

D.h. es gibt eine Darstellung

mit Primzahlen .

Beweis  

Wir beweisen die Existenz durch Induktion über .  Für liegt eine Primzahl vor. Bei ist entweder eine Primzahl, und diese bildet die Primfaktorzerlegung, oder aber ist keine Primzahl. In diesem Fall gibt es eine nichttriviale Zerlegung mit kleineren Zahlen . Für diese Zahlen gibt es nach Induktionsvoraussetzung jeweils eine Zerlegung in Primfaktoren, und diese setzen sich zu einer Primfaktorzerlegung für zusammen. 


Für beispielsweise findet man den Primfaktor und kann daher schreiben. Für hat man die Zerlegung und man erhält

Wenn man mit dem Primfaktor startet, so ergibt sich , insgesamt kommen also die gleichen Primfaktoren vor. Gelegentlich betrachten wir die Gleichung als die Primfaktorzerlegung der , hier tritt jeder Primfaktor mit dem Exponenten auf, das leere Produkt ist . Später werden wir zeigen, dass die Primfaktorzerlegung bis auf die Reihenfolge eindeutig ist, was keineswegs selbstverständlich ist, einiger Vorbereitungen bedarf und am besten innerhalb der ganzen Zahlen bewiesen wird.

Der folgende Satz wird Euklid zugeschrieben.



Satz  

Es gibt unendlich viele Primzahlen.

Beweis  

Angenommen, die Menge aller Primzahlen sei endlich, sagen wir sei eine vollständige Auflistung aller Primzahlen. Man betrachtet die natürliche Zahl

Da bei Division von durch immer der Rest übrigbleibt  (bzw. nach Aufgabe 12.6), ist diese Zahl durch keine der Primzahlen teilbar. Andererseits besitzt nach Satz 12.9 eine Primfaktorzerlegung. Insbesondere gibt es eine Primzahl , die teilt (dabei könnte sein). Doch damit muss gleich einem der aus der Liste sein, und diese sind keine Teiler von . Dies ist ein Widerspruch, da ein nicht gleichzeitig ein Teiler und kein Teiler von sein kann. Also muss die Annahme (nämlich die Endlichkeit der Primzahlmenge) falsch gewesen sein.




Primzahlprobleme

In der Vorlesung Grundkurs Mathematik geht es um Sachverhalte, die allesamt seit mindestens Jahren gut verstanden sind und zu einem großen Teil sogar bis in die griechische Antike zurückreichen. Wir unterbrechen die allgemeine Darstellung und gehen kurz auf die Frage ein, was Mathematiker in der Forschung machen. Das ist im Allgemeinen schwierig zu vermitteln, im zahlentheoretischen Kontext gibt es aber einige Beispiele, die sich leicht erläutern lassen.

Die treibende Kraft der Mathematik ist es, Probleme zu lösen. Schwierige Probleme gibt es in allen Bereichen der Mathematik, besonders prägnant sind sie in der Zahlentheorie, da es dort eine Vielzahl von elementar formulierten ungelösten Problemen gibt. Als Beispiel besprechen wir das Problem der Primzahlzwillinge, zu dem es kürzlich (2013) einen wichtigen Fortschritt gab.


Definition  

Ein Primzahlzwilling ist ein Paar bestehend aus und , wobei diese beiden Zahlen Primzahlen sind.

Die ersten Beispiele für Primzahlzwillinge sind

Übrigens ist der einzige Primzahldrilling, siehe Aufgabe 12.31.


Problem  

Gibt es unendlich viele Primzahlzwillinge?

Eine Lösung dieses Problems wäre ein mathematischer Satz, der entweder besagt, dass es unendlich viele Primzahlzwillinge gibt, oder dass es nur endlich viele Primzahlzwillinge gibt. D.h. das eine oder das andere müsste bewiesen werden. Bei schwierigen Problemen erwartet man nicht, dass jemand plötzlich einen Beweis hinschreibt, sondern dass eine neue und weit verzweigte Theorie entwickelt wird, mit der man letztlich einen Beweis geben kann.

Bemerkung  

Die Frage, ob es unendlich viele Primzahlzwillinge gibt, besitzt verschiedene schwächere Varianten. Man kann sich zum Beispiel fragen, ob es unendlich oft vorkommt, dass es in einem Zehnerintervall zwei Primzahlen gibt, oder dass es in einem Hunderterintervall zwei Primzahlen gibt, und so weiter. Die ersten Primzahlen vermitteln dabei ein Bild, dass Primzahlen ziemlich häufig sind. Sie werden aber zunehmend seltener, so dass es für hohe Hunderterintervalle, sagen wir für die Zahlen von

ziemlich unwahrscheinlich ist, eine Primzahl zu enthalten, geschweige denn zwei Primzahlen. Bis vor kurzem war es nicht bekannt, ob es überhaupt eine Zahl mit der Eigenschaft gibt, dass es unendlich viele Intervalle der Länge gibt, die zwei Primzahlen enthalten ( wäre die positive Lösung des Primzahlzwillingsproblems).

Im Jahr 2013 bewies Zhang Yitang, dass man
nehmen kann, dass es also unendlich viele Intervalle der Form
gibt, in denen zwei Primzahlen liegen. Dieses Resultat ist ein Durchbruch in der Primzahlzwillingforschung, da es erstmals zeigt, dass sich Primzahlen unendlich oft „ziemlich nahe“ kommen. Zwischenzeitlich wurde die Schranke von auf gesenkt, siehe [1].


<< | Kurs:Grundkurs Mathematik (Osnabrück 2016-2017)/Teil I | >>

PDF-Version dieser Vorlesung

Arbeitsblatt zur Vorlesung (PDF)