En Büyük Ortak Bölen
İki tam sayının en büyük ortak böleni (EBOB), her iki sayıyı da kalansız bölen ve kendisinden büyük, her iki sayıyı da kalansız bölen başka bir sayı bulunmayan sayıdır.
Örnek olarak 24 ve 32 sayılarını alalım. En büyük ortak bölenleri kaçtır? Önce her iki sayıyı da bölen bir sayı arıyoruz.
- Örneğin 12 sayısı 24’ü böler ama 32’yi bölmez, çünkü 32 / 12 işleminin sonucu 2,666… çıkar ve bu bir tam sayı değildir. Yani 12 sayısı 24 ile 32’nin en büyük ortak böleni olamaz.
- Peki ya 4? Bu sayı her ikisini de böler: 24 / 4 işleminin sonucu 6, 32 / 4 işleminin sonucu 8’dir. Demek ki 4 ilk adayımız. Her iki sayıyı da bölen daha büyük bir sayı var mı?
- 8 sayısı hem 24’ü hem de 32’yi böler ve 4’ten büyüktür.
- 8’den büyük, her iki sayıyı da bölen başka bir sayı yoktur. Yani 24 ile 32’nin en büyük ortak böleni 8’dir.
En Büyük Ortak Böleni Bulmak İçin Öklid Algoritması
İki sayının en büyük ortak bölenini Öklid algoritmasıyla bulmanın oldukça kolay bir yolu vardır. Başta, en büyük ortak bölenini bulmak istediğimiz iki sayı x ve y olsun. Örnek olarak bunu x = 50 ve y = 35 sayılarıyla deneyelim. Şöyle ilerleriz:
- x / y bölmesini yapar ve bölmeden kalanı aklımızda tutarız. Bu kalanı z diye not ederiz. Örneğimizde 50 / 35 işleminden z = 15 kalanını buluruz.
- Şimdi değişkenleri kaydırırız: x değişkenine y değerini, y değişkenine ise z değerini yazarız. x’in eski değerini atarız. Bu adımdan sonra x = 35 ve y = 15 olur.
- Şimdi y sıfıra eşit mi diye bakarız. Eşitse en büyük ortak bölen x sayısıdır. y sıfıra eşit olmadığı için devam eder ve bütün işlemi birinci adımdan yeniden tekrarlarız.
- Yine x / y bölmesini yaparız, yani 35 / 15 işleminden kalan z = 5 çıkar.
- Değişkenleri kaydırırız, yani x = 15 ve y = 5 olur. y sıfıra eşit olmadığı için devam ederiz.
- x / y bölmesini yaparız, yani 15 / 5. Kalan z = 0 olur.
- Değişkenleri kaydırırız ve x = 5, y = 0 elde ederiz.
- Şimdi y = 0 olduğu için algoritma sona erer. En büyük ortak bölen x = 5 sayısıdır.
Önemli olan, sayıların sırasının fark etmemesidir. Örnekteki sayıların yerlerini değiştirseydik x = 35 ve y = 50 çiftini elde ederdik. İşlem aynı olurdu:
- x / y bölmesini yaparız, yani 35 / 50 işleminden kalan z = 35 çıkar.
- Değişkenleri kaydırırız: x = 50 ve y = 35 olur.
- Bu adımdan sonra yalnızca x ve y değişkenlerinin içeriklerini birbiriyle değiştirmiş olduğumuzu görüyoruz…
Hesap Makinesi
Bu hesap makinesi en büyük ortak böleni hesaplar.
