Primfaktorzerlegung
\(~\)
Wir machen einen kleinen Abstecher in die Menge der natürlichen Zahlen
\(\quad \mathbb N=\{1,2,3,4,5,\dots\}\).
Diese spielen eine wichtige Rolle in der Mathematik und ein grundlegendes Verständnis für sie ist essentiell.
Eine fundamentale Rolle spielen dabei die Primzahlen.
\(~\)
|
Primzahlen Eine natürliche Zahl größer als 1 heißt Primzahl, wenn sie nur durch 1 und durch sich selbst teilbar ist. Hier sind einmal die ersten Primzahlen aufgelistet. \(\quad 2,3,5,7,11,13,17,19,\dots\) Die Liste der Primzahlen hört nicht auf, d.h. es gibt unendlich viele. |
\(~\)
Folgende Erkenntnis ist von großer Bedeutung für den Umgang mit Zahlen:
\(~\)
|
Primfaktorzerlegung Jede natürliche Zahl größer als 1 lässt sich auf eindeutige Art und Weise als Produkt von Primzahlen schreiben. Diese "Zerlegung" der Zahl in Faktoren, welche allesamt Primzahlen sind, wird Primfaktorzerlegung dieser Zahl genannt. |
\(~\)
|
Beispiel Um die Primfaktoren einer Zahl zu bestimmen, überprüft man am besten der Reihe nach die Teilbarkeit auf 2,3,5, usw., bis am Ende nur noch eine Primzahl übrig bleibt. Als Beispiel betrachten wir die Zahl \(360\). Diese ist offenbar durch 2 teilbar. Auch \(180\) und \(90\) sind wieder durch 2 teilbar: \(\quad 360=2\cdot 180=2\cdot2\cdot90=2\cdot2\cdot2\cdot45\). Schließlich können wir noch durch 3 teilen: \(\quad 360=2\cdot2\cdot2\cdot45=2\cdot2\cdot2\cdot3\cdot15=2\cdot2\cdot2\cdot3\cdot3\cdot5\). Die Primfaktorzerlegung der Zahl \(360\) lautet also \(2\cdot2\cdot2\cdot3\cdot3\cdot5\) oder, etwas kompakter, \(2^3\cdot 3^2\cdot 5^1\). \(~\) Die Primteiler selbst, die Zahl 1 sowie alle möglichen Produkte der Primteiler sind Teiler von 360. Teiler von 360 sind also beispielsweise 2, 3 und 5, aber auch 4, 6, 8, 9, 12, 15, 45 und 90 - nur um ein paar aufzuzählen. |
\(~\)
Die Primteiler einer relativ kleinen Zahl zu bestimmen ist ziemlich einfach, wie in obigem Beispiel veranschaulicht.
Man kann sich leicht vorstellen, dass dies für große Zahlen sehr aufwändig wird.
\(~\)
Anwendungen der Primfaktorzerlegung
\(~\)
1. Kürzen von Brüchen
\(~\)
Ein Bruch heißt vollständig bzw. weitestgehend gekürzt, wenn Nenner und Zähler keine gemeinsamen Teiler haben.
Der Bruch \(\dfrac 64\) kann beispielsweise noch zu \(\dfrac 32\) vereinfacht werden, da sowohl Nenner als auch Zähler durch 2 teilbar sind.
Um einen gegebenen Bruch weitestgehend zu kürzen, kann man beispielsweise Zähler und Nenner in seine Primfaktoren zerlegen und dann alle gemeinsamen Teiler kürzen.
\(~\)
|
Beispiele \(\quad\dfrac{42}{60}=\dfrac{2\cdot3\cdot7}{2\cdot2\cdot3\cdot 5}=\dfrac{7}{2\cdot 5}=\dfrac{7}{10}\). \(\quad\dfrac{10}{21}=\dfrac{2\cdot 5}{3\cdot7}\) ... dieser Bruch kann nicht weiter gekürzt werden. |
\(~\)
2. Größter gemeinsamer Teiler und kleinstes gemeinsames Vielfaches
\(~\)
|
Größter gemeinsamer Teiler Gegeben seien zwei natürliche Zahlen \(n\) und \(m\). Die größte natürliche Zahl \(z\), welche sowohl Teiler von \(n\) als auch von \(m\) ist, wird größter gemeinsamer Teiler von \(n\) und \(m\) genannt. Man schreibt auch \(\quad z=\mathrm{ggT}(n,m)\). |
\(~\)
Den größten gemeinsamen Teiler kann man beispielsweise aus den Primfaktorzerlegungen der beiden gegebenen Zahlen ablesen.
Dieser ergibt sich nämlich aus dem Produkt aller gemeinsamen Primfaktoren.
\(~\)
|
Beispiele Wir betrachten die Zahlen \(45\) und \(60\). Diese zerlegen wir zunächst beide in deren Primfaktoren. \(\quad 45=3\cdot\color{blue}{3}\cdot\color{red}{5}\). \(\quad 60=2\cdot2\cdot\color{blue}{3}\cdot\color{red}{5}\). Damit erhalten wir \(\quad\mathrm{ggT}(45,60)=\color{blue}{3}\cdot\color{red}{5}=15\). \(~\) Wir betrachten noch die Zahlen \(\quad 20=\color{blue}{2}\cdot\color{red}{2}\cdot5\quad\) und \(\quad 24=\color{blue}{2}\cdot\color{red}{2}\cdot3\) und erhalten \(\quad\mathrm{ggT}(20,24)=\color{blue}{2}\cdot\color{red}{2}=4\). |
\(~\)
|
Kleinstes gemeinsames Vielfaches Gegeben seien zwei natürliche Zahlen \(n\) und \(m\). Die kleinste natürliche Zahl \(z\), welche sowohl \(n\) als auch \(m\) als Teiler besitzt, wird kleinstes gemeinsames Vielfaches von \(n\) und \(m\) genannt. Man schreibt auch \(\quad z=\mathrm{kgV}(n,m)\). |
\(~\)
Auch das kleinste gemeinsame Vielfache lässt sich aus der Primfaktorzerlegung ableiten.
Um das kleinste gemeinsame Vielfache zu berechnen, bildet man das Produkt aller Primfaktoren, welche Teiler von mindestens einer der beiden gegebenen Zahlen sind.
Bei Primfaktoren, die Teiler von beiden Zahlen sind, müssen diese also mit der maximalen Potenz (Anzahl) in das Produkt eingehen.
\(~\)
|
Beispiele Wir betrachten die Zahlen \(\begin{array}{l}
Das kleinste gemeinsame Vielfache ergibt sich hier wie folgt. \(\quad \mathrm{kgV}(120,252)=\color{blue}{2^3}\cdot\color{red}{3^2}\cdot\color{green}{5^1}\cdot\color{violet}{7^1}=2520\). |
\(~\)
|
Bemerkung Analog ist der ggT und das kgV für mehr als zwei Zahlen definiert und bestimmbar. |
\(~\)
Bedeutung für die Bruchrechnung:
In einem Bruch kann man den ggT von Zähler und Nenner herauskürzen. Der resultierende Bruch ist dann weitestgehend gekürzt.
Das kgV aller Nenner verschiedener Brüche ist gerade der Hauptnenner (der kleinstmögliche Nenner, auf den die Brüche allesamt erweitert werden können, siehe Addition von Brüchen).
\(~\)
|
Übung: Führe nun den Selbsttest zum Thema Primzahlen und Primfaktorzerlegung durch. |
\(~\)
3. Weiteres
\(~\)
Primzahlen und die Primfaktorzerlegung sind nicht nur eine mathematische Spielerei.
Die Primfaktorisierung hat beispielsweise spannende Anwendungen in der Kryptographie / Verschlüsselungstheorie.
So basieren eine Reihe gängiger Verschlüsselungsalgorithmen (z.B. die sogenannte RSA-Kryptographie) auf der Primfaktorzerlegung sehr großer Zahlen.
Das Produkt zweier großer Primfaktoren zu berechnen ist einfach. Jedoch ist das umgekehrte Problem sehr viel komplizierter und aufwändiger:
Finde die Primfaktorzerlegung einer sehr großen Zahl, welche nur sehr wenige (im Idealfall zwei große) Primteiler hat.
Genau auf diesem Prinzip beruhen derartige Verschlüsselungsalgorithmen.