Rechner für teilerfremde Zahlen

Rechner für teilerfremde Zahlen

Beliebt AI Skill PRO

Geben Sie die Berechnung ein

Formel

Coprime⇔gcd⁡(a,b)=1\text{Coprime} \iff \gcd\left(\text{a},\ \text{b}\right) = 1

Beispiel

Coprime⇔gcd⁡(12,35)=1=1\text{Coprime} \iff \gcd\left(12,\ 35\right) = 1 = 1
Nutzungsstatistik

Werbung

Ergebnisse

Sind 12 und 35 teilerfremd?
Ja
gcd(12, 35) = 1
Größter gemeinsamer Teiler 1
Teilerfremd Ja (gcd = 1)

Fehler auf dieser Seite melden

Was ist der Rechner für teilerfremde Zahlen?

Zwei ganze Zahlen sind teilerfremd (auch koprim genannt), wenn die einzige positive ganze Zahl, die beide teilt, die 1 ist. Anders ausgedrückt ist ihr größter gemeinsamer Teiler (ggT) genau 1. Dieser Rechner nimmt zwei ganze Zahlen entgegen und zeigt sofort an, ob sie teilerfremd sind, zusammen mit ihrem ggT.

So verwenden Sie den Rechner

Geben Sie Ihre beiden ganzen Zahlen in die Felder für a und b ein und senden Sie das Formular ab. Das Tool berechnet \(\gcd(a, b)\) mithilfe des euklidischen Algorithmus. Ist der ggT 1, sind die Zahlen teilerfremd; andernfalls haben sie einen gemeinsamen Faktor und sind nicht koprim. Negative Vorzeichen werden ignoriert, da die Teilerfremdheit nur von den Beträgen abhängt.

Die Formel erklärt

Der euklidische Algorithmus ersetzt das Paar \((a, b)\) wiederholt durch \((b, a \bmod b)\), bis der zweite Wert 0 wird. Der letzte von null verschiedene Wert ist der ggT. Die Zahlen sind genau dann teilerfremd, wenn dieser ggT gleich 1 ist:

$$\text{Teilerfremd} \iff \gcd\left(\text{a},\ \text{b}\right) = 1$$

Zum Beispiel haben 8 und 15 keine gemeinsamen Primfaktoren, daher gilt \(\gcd = 1\) und sie sind teilerfremd, obwohl keine der beiden selbst eine Primzahl ist.

Werbung
Zwei Zahlen, die nur den gemeinsamen Faktor 1 haben, dargestellt als überlappende Faktorenmengen
Zwei Zahlen sind teilerfremd, wenn ihr einziger gemeinsamer Faktor 1 ist, also \(\gcd(a, b) = 1\).

Ausgearbeitetes Beispiel

Nehmen Sie \(a = 12\) und \(b = 35\). Die Faktoren von 12 sind 2 und 3; die Faktoren von 35 sind 5 und 7. Sie haben keinen gemeinsamen Primfaktor, also gilt \(\gcd(12, 35) = 1\). Daher sind 12 und 35 teilerfremd. Dagegen haben 12 und 18 den Faktor 6 gemeinsam, also gilt \(\gcd = 6\) und sie sind nicht koprim.

Schritte des euklidischen Algorithmus, die zwei Zahlen auf den ggT 1 reduzieren
Der euklidische Algorithmus verkleinert das Paar schrittweise, bis der Rest \(\gcd = 1\) zeigt.

Weitere Beispiele für teilerfremde Zahlen

Der euklidische Algorithmus ersetzt das Paar \((a,\ b)\) wiederholt durch \((b,\ a \bmod b)\), bis der Rest \(0\) ist. Der letzte von null verschiedene Rest ist \(\gcd(a,b)\), und das Paar ist genau dann teilerfremd, wenn dieser Wert \(1\) ist.

Beispiel 1 — ein großes teilerfremdes Paar: gcd(1071, 1024)

  1. \(1071 \bmod 1024 = 47\)
  2. \(1024 \bmod 47 = 37\)  (denn \(47 \times 21 = 987\) und \(1024 - 987 = 37\))
  3. \(47 \bmod 37 = 10\)
  4. \(37 \bmod 10 = 7\)
  5. \(10 \bmod 7 = 3\)
  6. \(7 \bmod 3 = 1\)
  7. \(3 \bmod 1 = 0\) → Stopp

Der letzte von null verschiedene Rest ist \(1\), also gilt \(\gcd(1071, 1024) = \) 1. Ergebnis: 1071 und 1024 sind teilerfremd (koprim) — obwohl keine der beiden eine Primzahl ist (\(1071 = 3 \times 3 \times 7 \times 17\) und \(1024 = 2^{10}\)), haben sie keinen gemeinsamen Primfaktor.

Beispiel 2 — ein nicht teilerfremdes Paar: gcd(84, 126)

  1. \(84 \bmod 126 = 84\), daher vertauscht der erste Schritt lediglich das Paar zu \((126,\ 84)\)
  2. \(126 \bmod 84 = 42\)
  3. \(84 \bmod 42 = 0\) → Stopp

Der letzte von null verschiedene Rest ist \(42\), also gilt \(\gcd(84, 126) = \) 42. Ergebnis: 84 und 126 sind NICHT teilerfremd. Die Primfaktorzerlegung bestätigt dies: \(84 = 2^2 \times 3 \times 7\) und \(126 = 2 \times 3^2 \times 7\), also ist der gemeinsame Anteil \(2 \times 3 \times 7 = 42\). Beachten Sie, dass das Voranstellen der kleineren Zahl nur einen zusätzlichen Vertauschungsschritt kostet — der Algorithmus verlangt keine geordneten Eingaben.

Beispiel 3 — zwei zusammengesetzte Zahlen, die dennoch teilerfremd sind: gcd(25, 54)

  1. \(54 \bmod 25 = 4\)  (denn \(25 \times 2 = 50\) und \(54 - 50 = 4\))
  2. \(25 \bmod 4 = 1\)  (denn \(4 \times 6 = 24\) und \(25 - 24 = 1\))
  3. \(4 \bmod 1 = 0\) → Stopp

Der letzte von null verschiedene Rest ist \(1\), also gilt \(\gcd(25, 54) = 1\). Ergebnis: 25 und 54 sind teilerfremd. Hier gilt \(25 = 5^2\) und \(54 = 2 \times 3^3\); die Primfaktormengen \(\{5\}\) und \(\{2, 3\}\) sind disjunkt. Das ist der entscheidende Punkt bei der Teilerfremdheit: Sie ist eine Eigenschaft eines Paares, nicht der einzelnen Zahlen — keine der beiden Zahlen muss eine Primzahl sein.

Werbung

Was Ihr Ergebnis bedeutet

Der Rechner gibt eine einzige Zahl aus, \(d = \gcd(a,b)\), und das Ergebnis richtet sich danach, ob \(d\) gleich \(1\) ist. Jeder Fall bringt eine bestimmte Reihe standardmäßiger zahlentheoretischer Folgerungen mit sich.

Wenn gcd(a, b) = 1 — die Zahlen sind teilerfremd

  • Der Bruch \(a/b\) ist bereits vollständig gekürzt. Es gibt keine ganze Zahl größer als \(1\), die aus Zähler und Nenner herausgekürzt werden kann.
  • \(a\) besitzt ein modulares multiplikatives Inverses mod \(b\) (und \(b\) besitzt eines mod \(a\)): Die Kongruenz \(a \cdot x \equiv 1 \pmod b\) ist lösbar, mit einer eindeutigen Lösung unter den Resten \(0, 1, \ldots, b-1\). Dies folgt aus der Bézout-Identität, die ganze Zahlen \(x, y\) garantiert mit $$a x + b y = 1$$ Reduziert man diese Gleichung mod \(b\), bleibt \(a x \equiv 1\). Für \(a = 25\), \(b = 54\): \(25 \cdot 13 - 54 \cdot 6 = 325 - 324 = 1\), also ist das Inverse von \(25\) mod \(54\) gleich \(13\).
  • Das kgV ist das einfache Produkt: \(\operatorname{lcm}(a,b) = a \cdot b\). Mit \(25\) und \(54\) gilt \(\operatorname{lcm} = 25 \times 54 = 1350\).
  • Der Chinesische Restsatz gilt für die Moduln \(a\) und \(b\). Jedes System \(x \equiv r \pmod a\), \(x \equiv s \pmod b\) besitzt eine Lösung, eindeutig modulo \(a \cdot b\) — z. B. eindeutig mod \(1350\) für die Moduln \(25\) und \(54\).
  • Schrittweises Weitergehen um \(a\) in einem Zyklus der Länge \(b\) besucht jede Position. Die Vielfachen \(0, a, 2a, 3a, \ldots\), modulo \(b\) reduziert, durchlaufen alle \(b\) Reste, bevor sie sich wiederholen; \(a\) erzeugt den vollständigen Zyklus. Wäre der ggT \(d > 1\), würde der Weg nur die \(b/d\) Positionen treffen, die durch \(d\) teilbar sind.
  • Gleichwertig: Die Primfaktorzerlegungen von \(a\) und \(b\) haben keine gemeinsame Primzahl, und \(a\) wird von der eulerschen Phi-Funktion \(\varphi(b)\) gezählt.

Wenn gcd(a, b) = d > 1 — die Zahlen sind nicht teilerfremd

  • Der Bruch \(a/b\) lässt sich kürzen. Division beider Teile durch \(d\) ergibt \((a/d)\,/\,(b/d)\), und dieses Paar ist teilerfremd, der gekürzte Bruch ist also vollständig gekürzt. Mit \(a = 84\), \(b = 126\), \(d = 42\): \(84/126 = 2/3\), und \(\gcd(2,3) = 1\).
  • Ein modulares Inverses von \(a\) mod \(b\) existiert nicht. Die Kongruenz \(a \cdot x \equiv 1 \pmod b\) hat keine Lösung, denn jeder Wert von \(a x - 1\), der ein Vielfaches von \(b\) ist, würde \(d \mid 1\) erzwingen. Allgemeiner ist \(a x \equiv c \pmod b\) nur lösbar, wenn \(d \mid c\), und dann hat sie genau \(d\) Lösungen mod \(b\).
  • Das kgV ist kleiner als das Produkt: \(\operatorname{lcm}(a,b) = \dfrac{a \cdot b}{d}\). Für \(84\) und \(126\): \(\operatorname{lcm} = \dfrac{84 \times 126}{42} = \dfrac{10584}{42} = 252\).
  • Die Bézout-Identität gilt weiterhin, jedoch in der Form \(a x + b y = d\) — der kleinste positive Wert, den \(a x + b y\) annehmen kann, ist \(d\), niemals \(1\). Der Chinesische Restsatz in seiner einfachen Form ist auf die Moduln \(a\) und \(b\) nicht anwendbar.

Grenzfälle

  • \(\gcd(1, n) = 1\) für jede ganze Zahl \(n\), daher ist \(1\) zu allem teilerfremd, einschließlich \(0\) und sich selbst: \(\gcd(1,1) = 1\).
  • \(\gcd(0, n) = |n|\), weil jede ganze Zahl \(0\) teilt. Daher ist \(0\) nur mit \(1\) und \(-1\) teilerfremd.
  • \(\gcd(0, 0)\) hat keinen größten gemeinsamen Teiler — jede ganze Zahl teilt \(0\), daher ist die Menge der gemeinsamen Teiler unbeschränkt. Konventionell wird er als \(0\) definiert, und das Paar \((0,0)\) ist nicht teilerfremd.
  • Das Vorzeichen spielt keine Rolle: \(\gcd(a,b) = \gcd(|a|, |b|)\), also gilt \(\gcd(-25, 54) = 1\) ebenso wie \(\gcd(25, 54) = 1\).
  • Eine Zahl ist nur dann zu sich selbst teilerfremd, wenn \(|a| = 1\) ist, da \(\gcd(a,a) = |a|\).

Konventionen und Grenzfälle

Jeder Fall unten wurde mit diesem Rechner durchgerechnet; die Ergebnisspalte zeigt, was er tatsächlich liefert.

FallEingabeErgebnis
1 und 91, 9Ja
0 und 50, 5Nein

Geprüft am 2026-11-08

FAQ

Müssen teilerfremde Zahlen Primzahlen sein? Nein. Teilerfremd bedeutet, dass sie keinen gemeinsamen Faktor größer als 1 haben; die Zahlen selbst müssen nicht prim sein (z. B. 8 und 9).

Ist 1 zu jeder Zahl teilerfremd? Ja. \(\gcd(1, n) = 1\) für jede ganze Zahl \(n\), daher ist 1 zu jeder ganzen Zahl teilerfremd.

Können zwei gerade Zahlen jemals teilerfremd sein? Nein. Zwei gerade Zahlen teilen stets den Faktor 2, daher ist ihr ggT mindestens 2.

Zuletzt aktualisiert:

Am beliebtesten in Mathe und Statistik

Alle Mathe und Statistik Rechner anzeigen