=== Bevis for korrekthed ===
Gyldigheden af Euklids algoritme kan bevises ved et to-trins argument.<ref>{{Harvnb|Stark|1978|pp=16–20}}</ref> I det første trin vises, at den sidste rest <math>r_{N-1}</math>, der altså er forskellig fra nul, går op i både <math>a</math> og <math>b</math>. Da det er en fælles divisor, skal den være mindre end eller lig med den største fælles divisor <math>g</math>. I det andet trin vises det, at enhver fælles divisor af <math>a</math> og <math>b</math>, inklusiv <math>g</math>, skal gå op i <math>r_{N-1}</math>, og derfor skal <math>g</math> være mindre end eller lig med <math>r_{N-1}</math>. Disse to konklusioner betyder sammen, at
:<math>r_{N-1}=g</math>
Religion Matematik