Theorie:
Betrachtet man zwei ganze Zahlen, so kann es sein, dass die erste ohne Rest durch die zweite Zahl teilbar ist. Ein Beispiel ist \(12\) und \(4\): Es gilt \(12:4=3\). In diesem Fall nennt man die zweite Zahl einen Teiler der ersten Zahl. In anderen Fällen lässt sich eine Division nicht ohne Rest durchführen, beispielsweise \(13:5\). Die Untersuchung solcher Teilbarkeitsfragen ist eines der Ziele dieses Kapitels.
Ist \(n\in\mathbb N\) und \(d\in\mathbb N\setminus\{0\}\), so heißt \(d\) Teiler von \(n\), wenn die Divison \(n/d\) ohne Rest durchführbar ist. Falls \(d\) ein Teiler von \(n\) ist, sagt man, dass \(n\) durch \(d\) teilbar ist, und schreibt \(d|n\). Ist \(d\) kein Teiler von \(n\), so drückt man das so aus: \(d\!\not |n\).
So ist in den obigen Beispielen \(4|12\) und \(5\!\not|13\).
Jede natürliche Zahl (ungleich null) ist durch \(1\) und sich selber teilbar.
Manche Zahlen sind aber auch noch durch andere Zahlen teilbar, wie man an Hand des obigen Beispiels \(12\) sehen kann. Andere, wie \(13\) sind durch keine anderen Zahlen mehr teilbar.
Eine natürliche Zahl \(n\ge 2\), die nur durch \(1\) und sich selber teilbar ist, heißt Primzahl.
Primzahlen spielen eine besondere Rolle, denn sie fungieren als "Bausteine" - jede natürliche Zahl ist eindeutig als Produkt von Primzahlen schreibbar.
Die Zerlegung einer natürlichen Zahl \(n\ge 2\) in das Produkt von Primzahlen nennt man Primfaktorzerlegung von \(n\).
So lässt sich \(12\) zerlegen als \(12=2\cdot 2\cdot 3\). Kommt ein Primfaktor \(p\) öfter als einmal vor (\(k\) mal), dann schreibt man \(p^k\). Das hochgestellte \(k\) signalisiert, wie oft der Faktor \(p\) in der Zahl vorkommt: \(p^k=\underbrace{p\cdots p}_{k\,\text{mal}}\). (Wir haben hier ein wenig die Potenz-Rechnung aus der nächsten Schulstufe vorweggenommen.) Wichtig an dieser Stelle ist folgende Regel:
\(p^k\cdot p^n = \underbrace{p\cdots p}_{k\,\text{mal}}\cdot \underbrace{p\cdots p}_{n\,\text{mal}} = \underbrace{p\cdots p}_{n+k\,\text{mal}} = p^{k+n}\).
Die ersten Primzahlen sind \(2,3,5,7,11\) und \(13\).
Es gibt unendlich viele Primzahlen.
Auch wenn zwischen \(2\) und \(10\) fast jede zweite Zahl eine Primzahl ist, werden die Primzahlen mit wachsender Zahl immer seltener.
Es ist möglich, die Häufigkeit von Primzahlen (wieviele Primzahlen \(p\le x\) es gibt, in Abhängigkeit der Schranke \(x\)) grob abzuschätzen (solche Untersuchungen gehören in das Gebiet der Zahlentheorie). Es gibt die Vermutung, dass sich diese Häufigkeit genauer als bisher möglich abschätzen ließe, aber seit über \(150\) Jahren konnte diese nicht bewiesen werden. Diese Vermutung zählt nun zu den berühmtesten (und schwierigsten) ungelösten Problemen der Mathematik. Die Untersuchung von Primzahlen ist jedoch nicht ein rein akademisches Problem - so basieren sehr viele heute verwendeten Verschlüsselungsverfahren auf Primzahlen.
Beispiel:
Die Primfaktorzerlegung der ersten paar natürlichen Zahlen, die keine Primzahlen sind, sind:
- \(4=2^2=2\cdot 2\)
- \(6=2\cdot 3\)
- \(8=2^3=2\cdot2\cdot 2\)
- \(9=3^2=3\cdot 3\)
- \(10=2\cdot 5\)
- \(12=2^2\cdot 3\)
- \(14=2\cdot 7\)
- \(15=3\cdot 5\)
- \(16=2^4=2\cdot 2\cdot 2\cdot 2\)
- \(18=2\cdot 3^2=2\cdot 3\cdot 3\)