Öklid Algoritması

Öklid, İskenderiye’de, milattan önce 3. ve 4. yüzyıllarda yaşamış çok ünlü bir matematikçidir. Eğitimini, Platon’un açmış olduğu ve zamanında matematik, doğa bilimleri ve yönetim gibi konular hakkında üst düzey, düşünme ve incelemeye dayalı derslerin verildiği bir kurum olan Akademi’de görmüştür. Akademi’deki eğitiminden sonra İskenderiye’de kendi matematik okulunu kurmuştur. Öklid Algoritması ise Öklid’in bulduğu matematik ile ilgili önemli ve dikkat çekici buluşlarından biridir.

Öklid Algoritması, iki sayının EBOB’unu (en büyük ortak bölen) bulmak için kullanılır.

Algoritmaya göre, iki sayının EBOB’u bulunurken ilk önce büyük sayı küçük sayıya bölünür. Bölümün sonucunda kalan 0 (sıfır) olur ise EBOB, küçük sayıya eşittir. Eğer 0’a eşit değil ise, küçük sayı, kalana bölünür ve kalan 0 olana dek bu işlemler tekrarlanır.

Örneğin 270 ve 192 sayılarını inceleyelim:

270 / 192 = 1 (78 kalan), yani 270 = 192 . 1 + 78

192 / 78 = 2 (36 kalan), yani 192 = 78 . 2 + 36

78 / 36 = 2 (6 kalan), yani 78 = 2 . 36 + 6

36 / 6 = 6 (kalan yok), yani 36 = 6 . 6

Buna göre: EBOB (270,192) = 6

Öklid algoritması yöntemi, her ne kadar uzun ve uğraştırıcı gibi gözüküyor olsa da, özellikle çok büyük sayılar incelenirken ve bazı diğer durumlarda büyük bir kolaylık sağlamaktadır. Çünkü bu yöntem ile en azından bir miktar daha küçük sayılarla çalışmaktayız ve her aşamada kullandığımız sayılar küçülmektedir.