Anzahl der Teiler, euklidischer Algorithmus, ggT und kgV

Inhalt
1. Anzahl der Teiler und Primfaktorzerlegung: die mathematische Formel
Wenn Sie alle Teiler einer sehr großen Zahl einzeln durch Probieren ermitteln wollen, kostet das viel Rechenaufwand und Zeit. Die Zahlentheorie umgeht das mithilfe der Primfaktorzerlegung auf elegante Weise.
Formel für die Anzahl der Teiler: Lässt sich eine natürliche Zahl N so in Primfaktoren zerlegen:
N = a^p × b^q × c^r × …(Dabei sind a, b, c verschiedene Primzahlen und p, q, r natürliche Zahlen als Exponenten.)
Anzahl der Teiler = (p + 1) × (q + 1) × (r + 1) × …Rechenbeispiel (Anzahl der Teiler von 72):
- Primfaktorzerlegung: 72 = 8 × 9 = 2^3 × 3^2
- Exponenten einsetzen: p = 3, q = 2
- Anzahl der Teiler: (3 + 1) × (2 + 1) = 4 × 3 = 12 Deutung des Ergebnisses: Sie müssen die Teiler von 72 nicht einzeln abzählen. Die Formel bestätigt, dass es insgesamt 12 sind (
1, 2, 3, 4, 6, 8, 9, 12, 18, 24, 36, 72).
2. Euklidischer Algorithmus und die Formeln für ggT und kgV
Der bekannteste Algorithmus, um den größten gemeinsamen Teiler zweier natürlicher Zahlen effizient zu bestimmen, ist der euklidische Algorithmus, der um 300 v. Chr. entstanden ist.
Rekursive Formel des euklidischen Algorithmus
Für zwei Zahlen a und b (a > b) gilt: Ist r der Rest bei der Division von a durch b, dann besteht folgende Identität:
ggT(a, b) = ggT(b, r)
Der Divisor, bei dem der Rest 0 wird, ist der gesuchte größte gemeinsame Teiler der beiden Zahlen.
- Beispiel (ggT(120, 36) bestimmen):
- 120 ÷ 36 = 3, Rest 12 → ggT(120, 36) = ggT(36, 12)
- 36 ÷ 12 = 3, Rest 0 → Da der Rest 0 ist, ist der letzte Divisor 12 der gesuchte größte gemeinsame Teiler.
Formel für das kleinste gemeinsame Vielfache
Kennen Sie den größten gemeinsamen Teiler (ggT), lässt sich das kleinste gemeinsame Vielfache (kgV) mit der folgenden Beziehung sofort berechnen:
kgV(a, b) = (a × b) ÷ ggT(a, b)
Anleitung: So nutzen Sie den Rechner für Teiler, ggT und kgV
Wenn Ihnen die Primfaktorzerlegung mehrstelliger Zahlen oder die wiederholten Divisionsschritte des euklidischen Algorithmus von Hand zu mühsam sind, können Sie ein spezielles Werkzeug für die Zahlentheorie nutzen.
Kostenlos · ohne Anmeldung · Teilerliste sowie ggT und kgV zweier Zahlen sofort nach der Eingabe

Die Bedienung ist ganz einfach:
- Zahlen eingeben: Tragen Sie die beiden natürlichen Zahlen, die Sie berechnen möchten, in die Felder „Zahl A“ und „Zahl B“ ein (Bereich 1 bis 10 Millionen).
- Schon während der Eingabe erscheinen im Analysebereich die Teilerlisten von A und B, die gemeinsamen Teiler und die Primfaktorzerlegung.
- Gleichzeitig werden in den Ergebniskarten oben ggT und kgV hervorgehoben dargestellt. Den Rechenweg über die Primfaktoren können Sie Schritt für Schritt nachvollziehen.
Fazit
Teiler, ggT und kgV wirken wie Grundschulmathematik, bilden aber das Fundament der digitalen Welt: Sie kommen bei den Grundrechenarten mit Brüchen, bei Bitoperationen und Zahlensystemen in der Informatik sowie bei der Verschlüsselung in der Informationssicherheit zum Einsatz. Bei mehrstelligen Zahlen schleichen sich von Hand leicht Fehler ein. Wenn Sie Ihr Ergebnis des euklidischen Algorithmus mit dem Rechner abgleichen, erkennen Sie Rechenfehler schnell.
Kostenlos · ohne Anmeldung · Teilerliste sowie ggT und kgV zweier Zahlen sofort nach der Eingabe
Häufige Fragen
Wie nennt man zwei natürliche Zahlen mit dem ggT 1, und warum ist das wichtig?
Haben zwei Zahlen außer 1 keinen gemeinsamen Teiler, ist ihr ggT also 1, nennt man sie mathematisch teilerfremd (englisch: coprime).
- Teilerfremdheit ist das zentrale Kriterium, wenn Sie einen Bruch bis zum nicht weiter kürzbaren Bruch kürzen.
- Besonders in der Kryptografie (RSA) wählt man zwei große Primzahlen und bildet ihr Produkt n. Für den öffentlichen Schlüssel verwendet man dann eine ganze Zahl, die zu einem aus n abgeleiteten Wert teilerfremd ist. Der Test auf Teilerfremdheit ist damit eine grundlegende Voraussetzung bei der Erzeugung von Schlüsseln.
Wie berechne ich ggT und kgV von drei oder mehr Zahlen (z. B. A, B, C)?
Der Rechner nimmt jeweils zwei Zahlen auf einmal entgegen. Bei drei oder mehr Zahlen geben Sie daher immer zwei Zahlen nacheinander ein und verwenden das Ergebnis für den nächsten Schritt.
Erweiterung der ggT-Formel:
ggT(A, B, C) = ggT(ggT(A, B), C)(Das heißt: Berechnen Sie zuerst den ggT von A und B im Rechner. Geben Sie dann dieses Ergebnis zusammen mit C erneut ein, erhalten Sie den ggT aller drei Zahlen.)
Erweiterung der kgV-Formel:
kgV(A, B, C) = kgV(kgV(A, B), C)Bestimmen Sie auf dieselbe Weise zuerst das kgV von A und B und geben Sie es dann zusammen mit C erneut in den Rechner ein. So lässt sich das Verfahren schrittweise auf beliebig viele Zahlen ausweiten.
Dieser Beitrag beruht auf anerkannten mathematischen Grundlagen der Zahlentheorie wie dem euklidischen Algorithmus und dient ausschließlich der Information.
Dieser Artikel basiert auf unserem koreanischen Original. Koreanisches Original lesen