Öklid Algoritması

Matematik tarihi ve geometri tarihi yazı dizimize biraz ara verelim. Bugün farklı bir ipucu anlatmak istiyorum.Ben ipucu diyorum çünkü lise ve dengi okullarda okuyan arkadaşlarım için belki ilk defa görecekler bu yolu ve çok pratiktir aslında bölünebilme konusunda.Üniversitede okuyan arkadaşlarım için pek ipucu sayılmaz zira Sayılar Teorisi dersinin bir konusudur. Neyse lafı uzatmadan anlatım yapalım..
                                Devamı için başlığa tıklayınız.


İki sayının EBOB'unu bulmamız istendi diyelim. Ve sayılarda şu şekilde olsun. 30 ve 20.
Saıları basit vermemin nedeni tek seferde anlaşılması. Şimdi matematik dilinde 30 ve 20 nin EBOB'u (30,20) şeklinde gösterilir.(EKOK'u da [30,20] dir).
Yani,

(30,20) bulalım,

1.Adım

(30,20)
30=20.1+10

>>>Burada yaptığımız büyük sayı olan 30'u 20'nin cinsinden yazmak. 20.1=20 ve kalanda haliyle 10 olur.Yani 30=20.1+10


2.Adım   

30=20.1+10
20=10.2+0

>>>Görüldüğü gibi ikinci adımda bölen olan 20 sayısı bölünen yerine ve kalan olan 10 sayısı da bölen yerine geçti. Bu şekilde devam ederek en son kalan olarak 0 sayısını bulana kadar devam ediyoruz ve bulduğumuz 0 sayısından bir önceki adımda bulunan sayı bize EBOB'umuzu verir. Yani (30,20)=10 dur.

Farklı bir örnek çözelim;

(88,54) bulalım.

88=54.1+34
54=34.1+20
34=20.1+14
20=14.1+6
14=6.2+2
6=2.3+0 >>> 0 kalanını bulduk bir önceki adımda bulduğumuz kalan 2 olduğuna göre;

(88,54)=2 Yani 88 ve 54 sayılarının en büyük ortak bölenleri 2 dir.