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.