Grundlagen: Mathematik

Was berechnet der euklidische Algorithmus?

Der euklidische Algorithmus berechnet den größten gemeinsamen Teiler durch wiederholte Division mit Rest:

$$\gcd(a,b)=\gcd(b, a\bmod b).$$

Ende, wenn der Rest $0$ ist.