<?xml version="1.0"?>
<feed xmlns="http://www.w3.org/2005/Atom" xml:lang="de">
	<id>https://wiki.flbk-hamm.de/index.php?action=history&amp;feed=atom&amp;title=Euklidischer_Algorithmus</id>
	<title>Euklidischer Algorithmus - Versionsgeschichte</title>
	<link rel="self" type="application/atom+xml" href="https://wiki.flbk-hamm.de/index.php?action=history&amp;feed=atom&amp;title=Euklidischer_Algorithmus"/>
	<link rel="alternate" type="text/html" href="https://wiki.flbk-hamm.de/index.php?title=Euklidischer_Algorithmus&amp;action=history"/>
	<updated>2026-11-16T00:45:32Z</updated>
	<subtitle>Versionsgeschichte dieser Seite in FLBK-Wiki</subtitle>
	<generator>MediaWiki 1.46.2</generator>
	<entry>
		<id>https://wiki.flbk-hamm.de/index.php?title=Euklidischer_Algorithmus&amp;diff=3199&amp;oldid=prev</id>
		<title>Flbkwikiadmin: Die Seite wurde neu angelegt: „Der euklidische Algorithmus berechnet den größten gemeinsamen Teiler zweier Zahlen, ohne dass man ihre Teiler kennen muss. Er ist über zweitausend Jahre alt und eine Grundlage des RSA-Verfahrens.  ==Definition== Der &#039;&#039;&#039;größte gemeinsame Teiler&#039;&#039;&#039; zweier natürlicher Zahlen &lt;math&gt;a&lt;/math&gt; und &lt;math&gt;b&lt;/math&gt; ist die größte natürliche Zahl, durch die sich beide ohne Rest teilen lassen. Man schreibt &lt;math&gt;\operatorname{ggT}(a; b)&lt;/ma…“</title>
		<link rel="alternate" type="text/html" href="https://wiki.flbk-hamm.de/index.php?title=Euklidischer_Algorithmus&amp;diff=3199&amp;oldid=prev"/>
		<updated>2026-11-15T06:46:24Z</updated>

		<summary type="html">&lt;p&gt;Die Seite wurde neu angelegt: „Der euklidische Algorithmus berechnet den größten gemeinsamen Teiler zweier Zahlen, ohne dass man ihre Teiler kennen muss. Er ist über zweitausend Jahre alt und eine Grundlage des &lt;a href=&quot;/RSA-Verfahren&quot; title=&quot;RSA-Verfahren&quot;&gt;RSA-Verfahrens&lt;/a&gt;.  ==Definition== Der &amp;#039;&amp;#039;&amp;#039;größte gemeinsame Teiler&amp;#039;&amp;#039;&amp;#039; zweier natürlicher Zahlen &amp;lt;math&amp;gt;a&amp;lt;/math&amp;gt; und &amp;lt;math&amp;gt;b&amp;lt;/math&amp;gt; ist die größte natürliche Zahl, durch die sich beide ohne Rest teilen lassen. Man schreibt &amp;lt;math&amp;gt;\operatorname{ggT}(a; b)&amp;lt;/ma…“&lt;/p&gt;
&lt;p&gt;&lt;b&gt;Neue Seite&lt;/b&gt;&lt;/p&gt;&lt;div&gt;Der euklidische Algorithmus berechnet den größten gemeinsamen Teiler zweier Zahlen, ohne dass man ihre Teiler kennen muss. Er ist über zweitausend Jahre alt und eine Grundlage des [[RSA-Verfahren|RSA-Verfahrens]].&lt;br /&gt;
&lt;br /&gt;
==Definition==&lt;br /&gt;
Der &amp;#039;&amp;#039;&amp;#039;größte gemeinsame Teiler&amp;#039;&amp;#039;&amp;#039; zweier natürlicher Zahlen &amp;lt;math&amp;gt;a&amp;lt;/math&amp;gt; und &amp;lt;math&amp;gt;b&amp;lt;/math&amp;gt; ist die größte natürliche Zahl, durch die sich beide ohne Rest teilen lassen. Man schreibt &amp;lt;math&amp;gt;\operatorname{ggT}(a; b)&amp;lt;/math&amp;gt;.&lt;br /&gt;
&lt;br /&gt;
Der &amp;#039;&amp;#039;&amp;#039;euklidische Algorithmus&amp;#039;&amp;#039;&amp;#039; ist ein Verfahren, das den größten gemeinsamen Teiler durch wiederholte [[Modulo|Division mit Rest]] berechnet. Er ist nach dem griechischen Mathematiker Euklid benannt.&lt;br /&gt;
&lt;br /&gt;
==Teilerfremdheit==&lt;br /&gt;
Zwei Zahlen &amp;lt;math&amp;gt;a&amp;lt;/math&amp;gt; und &amp;lt;math&amp;gt;b&amp;lt;/math&amp;gt; heißen &amp;#039;&amp;#039;&amp;#039;teilerfremd&amp;#039;&amp;#039;&amp;#039;, wenn sie außer 1 keinen gemeinsamen Teiler haben, wenn also &amp;lt;math&amp;gt;\operatorname{ggT}(a; b) = 1&amp;lt;/math&amp;gt; gilt. Teilerfremde Zahlen müssen selbst keine Primzahlen sein.&lt;br /&gt;
&lt;br /&gt;
Beim RSA-Verfahren entscheidet die Teilerfremdheit darüber, ob ein Schlüsselpaar entsteht: Zur Zahl &amp;lt;math&amp;gt;e&amp;lt;/math&amp;gt; des öffentlichen Schlüssels gibt es genau dann eine passende Zahl &amp;lt;math&amp;gt;d&amp;lt;/math&amp;gt; für den privaten Schlüssel, wenn &amp;lt;math&amp;gt;e&amp;lt;/math&amp;gt; und &amp;lt;math&amp;gt;\varphi(N)&amp;lt;/math&amp;gt; teilerfremd sind (siehe [[RSA-Verfahren#Schlüsselerzeugung|Schlüsselerzeugung]] und [[Erweiterter euklidischer Algorithmus#Modulares Inverses|modulares Inverses]]).&lt;br /&gt;
&lt;br /&gt;
==Verfahren==&lt;br /&gt;
# Die größere Zahl wird durch die kleinere geteilt. Notiert wird die Division mit Rest: &amp;lt;math&amp;gt;a = k \cdot b + r&amp;lt;/math&amp;gt;.&lt;br /&gt;
# Danach wird der bisherige Teiler durch den Rest geteilt, wieder mit Rest.&lt;br /&gt;
# Das wiederholt sich, bis eine Division aufgeht, der Rest also 0 ist.&lt;br /&gt;
# Der letzte Rest, der nicht 0 ist, ist der größte gemeinsame Teiler. Er ist der Teiler der letzten Division.&lt;br /&gt;
&lt;br /&gt;
Die untereinander geschriebenen Divisionen heißen &amp;#039;&amp;#039;&amp;#039;Divisionskette&amp;#039;&amp;#039;&amp;#039;.&lt;br /&gt;
&lt;br /&gt;
Das Verfahren ist richtig, weil jeder gemeinsame Teiler von &amp;lt;math&amp;gt;a&amp;lt;/math&amp;gt; und &amp;lt;math&amp;gt;b&amp;lt;/math&amp;gt; auch den Rest &amp;lt;math&amp;gt;r = a - k \cdot b&amp;lt;/math&amp;gt; teilt und umgekehrt jeder gemeinsame Teiler von &amp;lt;math&amp;gt;b&amp;lt;/math&amp;gt; und &amp;lt;math&amp;gt;r&amp;lt;/math&amp;gt; auch &amp;lt;math&amp;gt;a&amp;lt;/math&amp;gt; teilt. Deshalb gilt&lt;br /&gt;
&lt;br /&gt;
:&amp;lt;math&amp;gt;\operatorname{ggT}(a; b) = \operatorname{ggT}(b; \; a \bmod b)&amp;lt;/math&amp;gt;&lt;br /&gt;
&lt;br /&gt;
Die Reste werden von Schritt zu Schritt kleiner, deshalb endet das Verfahren immer. Es endet sogar schnell: Nach je zwei Divisionen hat sich der Rest mindestens halbiert. Die Anzahl der Divisionen wächst deshalb nur mit der Stellenzahl der Zahlen. Auch bei Zahlen mit mehreren hundert Stellen sind es höchstens einige tausend Divisionen.&lt;br /&gt;
&lt;br /&gt;
Bei kleinen Zahlen führt auch ein Vergleich der &amp;#039;&amp;#039;&amp;#039;Teilerlisten&amp;#039;&amp;#039;&amp;#039; zum Ziel: Man schreibt alle Teiler beider Zahlen auf und sucht den größten, der in beiden Listen steht. Bei großen Zahlen ist das viel zu aufwendig, weil man dafür die Zahlen in Faktoren zerlegen müsste (siehe [[Primfaktorzerlegung]]).&lt;br /&gt;
&lt;br /&gt;
==Umsetzung in Java==&lt;br /&gt;
Die Schleife ersetzt das Zahlenpaar so lange durch den Teiler und den Rest, bis der Rest 0 ist (siehe [[Schleife#WHILE-Schleife|while-Schleife]]):&lt;br /&gt;
&lt;br /&gt;
&amp;lt;syntaxhighlight lang=&amp;quot;java&amp;quot;&amp;gt;&lt;br /&gt;
public static int ggT(int a, int b) {&lt;br /&gt;
    while (b != 0) {&lt;br /&gt;
        int rest = a % b;&lt;br /&gt;
        a = b;&lt;br /&gt;
        b = rest;&lt;br /&gt;
    }&lt;br /&gt;
    return a;&lt;br /&gt;
}&lt;br /&gt;
&amp;lt;/syntaxhighlight&amp;gt;&lt;br /&gt;
&lt;br /&gt;
Dieselbe Idee als [[Rekursion]], direkt nach der Formel &amp;lt;math&amp;gt;\operatorname{ggT}(a; b) = \operatorname{ggT}(b; \; a \bmod b)&amp;lt;/math&amp;gt;:&lt;br /&gt;
&lt;br /&gt;
&amp;lt;syntaxhighlight lang=&amp;quot;java&amp;quot;&amp;gt;&lt;br /&gt;
public static int ggTRekursiv(int a, int b) {&lt;br /&gt;
    if (b == 0) {&lt;br /&gt;
        return a;&lt;br /&gt;
    }&lt;br /&gt;
    return ggTRekursiv(b, a % b);&lt;br /&gt;
}&lt;br /&gt;
&amp;lt;/syntaxhighlight&amp;gt;&lt;br /&gt;
&lt;br /&gt;
==Beispiele==&lt;br /&gt;
===ggT mit der Divisionskette berechnen===&lt;br /&gt;
Gesucht ist der größte gemeinsame Teiler von 1071 und 1029.&lt;br /&gt;
&lt;br /&gt;
:&amp;lt;math&amp;gt;1071 = 1 \cdot 1029 + 42&amp;lt;/math&amp;gt;&lt;br /&gt;
:&amp;lt;math&amp;gt;1029 = 24 \cdot 42 + 21&amp;lt;/math&amp;gt;&lt;br /&gt;
:&amp;lt;math&amp;gt;42 = 2 \cdot 21 + 0&amp;lt;/math&amp;gt;&lt;br /&gt;
&lt;br /&gt;
Die letzte Division geht auf. Der letzte Rest, der nicht 0 ist, ist 21: &amp;lt;math&amp;gt;\operatorname{ggT}(1071; 1029) = 21&amp;lt;/math&amp;gt;.&lt;br /&gt;
&lt;br /&gt;
===Teilerfremdheit prüfen===&lt;br /&gt;
Sind 179 und 69 teilerfremd?&lt;br /&gt;
&lt;br /&gt;
:&amp;lt;math&amp;gt;179 = 2 \cdot 69 + 41&amp;lt;/math&amp;gt;&lt;br /&gt;
:&amp;lt;math&amp;gt;69 = 1 \cdot 41 + 28&amp;lt;/math&amp;gt;&lt;br /&gt;
:&amp;lt;math&amp;gt;41 = 1 \cdot 28 + 13&amp;lt;/math&amp;gt;&lt;br /&gt;
:&amp;lt;math&amp;gt;28 = 2 \cdot 13 + 2&amp;lt;/math&amp;gt;&lt;br /&gt;
:&amp;lt;math&amp;gt;13 = 6 \cdot 2 + 1&amp;lt;/math&amp;gt;&lt;br /&gt;
:&amp;lt;math&amp;gt;2 = 2 \cdot 1 + 0&amp;lt;/math&amp;gt;&lt;br /&gt;
&lt;br /&gt;
Die letzte Division geht auf. Der letzte Rest, der nicht 0 ist, ist 1: &amp;lt;math&amp;gt;\operatorname{ggT}(179; 69) = 1&amp;lt;/math&amp;gt;. Die beiden Zahlen sind teilerfremd.&lt;br /&gt;
&lt;br /&gt;
===ggT über Teilerlisten bestimmen===&lt;br /&gt;
* Teiler von 36: 1, 2, 3, 4, 6, 9, 12, 18, 36&lt;br /&gt;
* Teiler von 96: 1, 2, 3, 4, 6, 8, 12, 16, 24, 32, 48, 96&lt;br /&gt;
* gemeinsame Teiler: 1, 2, 3, 4, 6, 12&lt;br /&gt;
&lt;br /&gt;
Der größte gemeinsame Teiler ist &amp;lt;math&amp;gt;\operatorname{ggT}(36; 96) = 12&amp;lt;/math&amp;gt;. Der euklidische Algorithmus liefert dasselbe mit weniger Aufwand:&lt;br /&gt;
:&amp;lt;math&amp;gt;96 = 2 \cdot 36 + 24&amp;lt;/math&amp;gt;&lt;br /&gt;
:&amp;lt;math&amp;gt;36 = 1 \cdot 24 + 12&amp;lt;/math&amp;gt;&lt;br /&gt;
:&amp;lt;math&amp;gt;24 = 2 \cdot 12 + 0&amp;lt;/math&amp;gt;&lt;br /&gt;
&lt;br /&gt;
[[Kategorie:Kryptologie]]&lt;br /&gt;
[[Kategorie:Mathematik]]&lt;br /&gt;
[[Kategorie:AHR I Informatik LK]]&lt;/div&gt;</summary>
		<author><name>Flbkwikiadmin</name></author>
	</entry>
</feed>