Öklid algoritması, iki pozitif tam sayının en büyük ortak bölenini hesaplayan yöntemdir. Temel işlem, bir sayıyı diğerine bölüp kalanla devam etmektir. Sayıların bütün bölenlerini ayrı ayrı listelemek gerekmez. NIST'in algoritma sözlüğünde yöntem, ikinci sayı sıfır olduğunda birinci sayıyı döndüren; diğer durumlarda sayı çiftini ikinci sayı ve kalanla değiştiren bir işlem olarak tanımlanır.[1]
İŞLEYİŞ
a sayısının b ile bölümünden kalan r olsun. a ve b'nin ortak bölenleri, b ve r'nin ortak bölenleriyle aynıdır. Bu nedenle işlem daha küçük sayılarla sürdürülebilir. Kalan sıfıra ulaştığında, son sıfır olmayan kalan başlangıçtaki sayıların en büyük ortak bölenidir. Kalanların küçülmesi, işlemin sonlu adımda bitmesini sağlar.[1]
SAYISAL ÖRNEK
48 ve 18 için sırasıyla 48 = 2 × 18 + 12, 18 = 1 × 12 + 6 ve 12 = 2 × 6 + 0 elde edilir. Son sıfır olmayan kalan 6'dır. Dolayısıyla iki sayının en büyük ortak böleni 6 olur. Örnek, aynı kuralın her adımda tekrar uygulanmasını gösterir.[1]