2.1 Euklidischer Algorithmus

Der Euklidische Algorithmus berechnet den größten gemeinsamen Teiler (ggT) zweier positiver ganzer Zahlen (etwa r₀ , r₁ , wobei r₀ > r₁).
Der Algorithmus besteht aus der wiederholten Durchführung folgender ganzzahliger Division:

r0	= q1r1+r2 ,	0 < r2 < r1
r1	= q2 r2+r3 ,	0 < r3 < r2
	...
rm-2	= qm-1rm-1+rm ,	0 < rm < rm-1
rm-1	= qmrm .

Dann kann man leicht zeigen, daß

ggT( r₀ , r₁) = ggT( r₁ , r₂) = ... = ggT( r_m-1 , r_m) = r_m .

Da der Euklidische Algorithmus größte gemeinsame Teiler berechnet, kann man ihn verwenden, um festzustellen, ob eine positive ganze Zahl b < n ein multiplikatives Inverses modulo n besitzt, indem man r₀ = n und r₁ = b setzt.
Man erhält aber nicht den Wert des Inversen, sofern dieses überhaupt existiert.
Das leistet der Erweiterte Euklidische Algorithmus.

2.2 Erweiterter Euklidischer Algorithmus