Der Euklidischer Algorithmus ist ein Verfahren zur Bestimmung des ggT (GrößterGemeinsamerTeilers) zweier Zahlen. Er basiert auf der Modulorechnung.
Man nehme zwei Zahlen a & b, für die gilt a>=b
a mod b = r1
b mod r1 = r2
r1 mod r2 = r3
r2 mod r3 = r4
….usw.
bis
rn mod rn+1 = 0
dann: rn+1→ggT
ggT(35,25)=?
35 mod 25 = 10
25 mod 10 = 5
10 mod 5 = 0
⇒ 5=ggT(35,25)
Der gesamte Algorithmus basiert auf der schlichten Tatsache, dass der Rest von a/b (hier: r1) und b den selben ggT haben wie a und b. Und damit auch auch den selben wie der Rest aus b/r1 (hier: r2) und r1 und so weiter und so fort. Also muss die Modulorechnung „alter“ Divisor modulo „alter“ Rest so lange fortgeführt werden, bis rn ohne Rest durch rn+1 teilbar ist, weil dann rn+1 automatisch der ggT von sich selbst und rn ist. Im Bsp ist dies bei rn=10 und rn+1=5 erreicht.