EUKLIDISCHER ALGORITHMUS

euklidischer Algorịthmus

 

[nach Euklid], Verfahren zur Bestimmung des größten gemeinsamen Teilers zweier ganzrationaler Zahlen a, b (≠ 0); die Kettendivison

 

bricht nach endlich vielen Schritten ab und führt zu der Gleichung r_n = q_n+2 · r_n+1 + 0. Der gesuchte größte gemeinsame Teiler ist r_n+1.

 

Beispiel: a = 1 988, b = 1 065; dann ist

 

als größter gemeinsamer Teiler ergibt sich also 71.