Öklid algoritması

Öklid algoritması iki doğal sayının en büyük ortak bölenini bulmak için kullanılır.

Algoritma 
 olsun. 
 ve
 tanımları ile
 oluncaya kadar gidilir.
 ve son satırda  olduğundan
 sonucuna ulaşılır.
Her satırda elde edilen eşitlikler toplandığında 
 sonucu elde edilir.

Sayılar teorisi algoritmaları