Metraipolis › archive › dc_d02111a1309f

Erweiterter euklidischer Algorithmus — Wikipedia (de)

Source
Wikipedia (de)
Original
https://de.wikipedia.org/wiki/Erweiterter_euklidischer_Algorithmus
License (as archived)
CC-BY-SA-4.0
Archived
2026-10-31T14:32:06.272Z
SHA-256 of the archived text
670eb28b3b3e5715e1fb9b05d91a94a5f0e246f9b73227de887a2f93f4bf075d
Stable URL of this page
https://metraipolis.com/documento/dc_d02111a1309f

How to cite

Erweiterter euklidischer Algorithmus — Wikipedia (de) — Wikipedia (de), https://de.wikipedia.org/wiki/Erweiterter_euklidischer_Algorithmus (CC-BY-SA-4.0); archived copy: https://metraipolis.com/documento/dc_d02111a1309f (Metraipolis archive dc_d02111a1309f, sha256 670eb28b3b3e5715e1fb9b05d91a94a5f0e246f9b73227de887a2f93f4bf075d)
BibTeX
@misc{dcd02111a1309f,
  title = {Erweiterter euklidischer Algorithmus — Wikipedia (de)},
  howpublished = {Wikipedia (de)},
  url = {https://de.wikipedia.org/wiki/Erweiterter_euklidischer_Algorithmus},
  note = {License CC-BY-SA-4.0; archived copy https://metraipolis.com/documento/dc_d02111a1309f; sha256 670eb28b3b3e5715e1fb9b05d91a94a5f0e246f9b73227de887a2f93f4bf075d},
  year = {2026}
}

Archived text

Reproduced under CC-BY-SA-4.0. Attribution: Wikipedia (de), https://de.wikipedia.org/wiki/Erweiterter_euklidischer_Algorithmus. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

Der erweiterte euklidische Algorithmus ist ein Algorithmus aus dem mathematischen Teilgebiet der Zahlentheorie. Er berechnet neben dem größten gemeinsamen Teiler ggT ( a , b ) {\displaystyle \operatorname {ggT} (a,b)} zweier natürlicher Zahlen a {\displaystyle a} und b {\displaystyle b} noch zwei ganze Zahlen s {\displaystyle s} und t {\displaystyle t} , die die folgende Gleichung erfüllen: ggT ( a , b ) = s ⋅ a + t ⋅ b {\displaystyle \operatorname {ggT} (a,b)=s\cdot a+t\cdot b} Der Algorithmus ist eine Erweiterung des bereits in der Antike bekannten euklidischen Algorithmus, der nur den größten gemeinsamen Teiler berechnet. Das Haupteinsatzgebiet des erweiterten euklidischen Algorithmus ist die Berechnung der inversen Elemente in ganzzahligen Restklassenringen, denn wenn der Algorithmus das Tripel ( d = ggT ( a , b ) , s , t ) {\displaystyle (d=\operatorname {ggT} (a,b),s,t)} ermittelt, ist entweder d = 1 {\displaystyle d=1} und damit 1 ≡ t ⋅ b ( mod a ) {\displaystyle 1\equiv t\cdot b{\pmod {a}}} , t {\displaystyle t} also das multiplikative Inverse von b {\displaystyle b} modulo a , {\displaystyle a,} oder aber d ≠ 1 , {\displaystyle d\neq 1,} was bedeutet, dass b {\displaystyle b} modulo a {\displaystyle a} kein Inverses hat. Dies ist die Grundlage für die Lösung von diophantischen Gleichungen oder allgemeiner von ganzzahligen linearen Gleichungssystemen. Ebenso ist die Bestimmung inverser Elemente eine Grundlage für den chinesischen Restsatz, welcher wiederum Grundlage des bedeutenden Tricks der kleinen Primzahlen in der berechenbaren Algebra ist. Dabei wird eine Aufgabe in mehreren endlichen Körpern gelöst und diese Teillösungen in immer größere Restklassenringe gehoben, bis sich eine ganzzahlige Lösung ablesen lässt. Der Algorithmus liefert zudem einen konstruktiven Beweis für das Lemma von Bézout, also 1 = s ⋅ a + t ⋅ b {\displaystyle 1=s\cdot a+t\cdot b} . Die am weitesten bekannte Version des euklidischen Algorithmus bezieht sich auf den Bereich der ganzen Zahlen. Jedoch kann er auf jeden Ring angewandt werden, in welchem eine Division mit kleinstem Rest durchgeführt werden kann. Solche Ringe werden euklidisch genannt, ein Beispiel ist der Polynomring in einer Variablen mit rationalen oder reellen Koeffizienten. In diesem kann immer ein eindeutig bestimmter Rest mit kleinstem Grad gefunden werden.

Tema degli esploratori: matematica e informatica teorica (deposito sistematico; ricerca «Zahlentheorie»).
Fonte: Wikipedia in tedesco, voce «Erweiterter euklidischer Algorithmus» — https://de.wikipedia.org/wiki/Erweiterter_euklidischer_Algorithmus
Wikidata Q1362750 (dati Wikidata in CC0 1.0) — https://www.wikidata.org/wiki/Q1362750
Autori: i contributori di Wikipedia (cronologia: https://de.wikipedia.org/wiki/Erweiterter_euklidischer_Algorithmus?action=history).
Licenza: Creative Commons Attribuzione-Condividi allo stesso modo 4.0 (CC BY-SA 4.0) — https://creativecommons.org/licenses/by-sa/4.0/. Il riuso richiede attribuzione e stessa licenza.
Estratto dell'introduzione non modificato nel contenuto; revisione 269434886, consultata il 2026-10-31T14:21:10.162Z tramite l'API ufficiale di Wikipedia. Impronta SHA-256 dell'estratto: f4e6ad7904d4471e75048e7f32bdc2cacf7a0d734f25049a2bf616a051d8a4a9