Öklid Algoritması

Öklid Algoritması; (Bkz.Euclidin Hayatı) (MÖ.325-MÖ.265) tarafından bulunan kullanışlı bir bölüm işlevidir. EBOB bulma işlemlerinde genellikle asal çarpanlarına ayrılması yönteminden yararlanırız. Lakin bazı durumlarda bu asal çarpanlarına ayırma işlemi sıkıntılı olabilir. Özellikle büyük sayılar verildiğinde EBOB bulma işlemi, asal çarpan yönteminde daha zor hale gelebilir. İki tam sayının en büyük ortak bölenini bulmak için yapılan ardışık bölme işlemine öklit algoritması denir. Ardışık bölme işlemine kalan sıfır oluncaya kadar devam edilir. Sıfırdan önceki en son bölen sayı EBOB u verir. Öklid algoritmasında yapılması gereken temel mantık; ardışık olarak büyük sayıyı küçük sayıya bölerek kalanın 0 olması durumuna kadar devam edilmesidir. Bazı durumlarda kalan 0 olmayabilir bu durumlarda farklı çözüm yolları geliştirilmelidir. 

<<<NOT>>>Öklid Algoritmasına göre herhangi iki sayının A ve B sayılarının EBOB'ları bilinirse buna bağlı olarak şu ifadeleri de Öklid Algoritmasının bir sonucu olarak söyleyebiliriz. Bu özellikler büyük sayıların verildiği soruların çözümünde kolaylık sağlayacaktır.
>>>  k, bir tamsayı olmak üzere; 

** EBOB(A,B)=EBOB(A, A-B.k)

** EBOB(A,B)=EBOB(A, A-B) 

** EBOB(A,B)=EBOB(A, A+B)

Aşağıdaki örnekler üzerinde incelemelerde bulunarak, Öklid Algoritmasının nasıl uygulandığını daha iyi anlatmaya çalışalım. Örnekleri inceledikten sonra aşağıda çözümsüz olarak verilen benzer soruları kendiniz çözmeye çalışınız.

---

ÖRNEK: En basit haliyle 140 ve 36 sayılarının EBOB'unu öklid algoritması ile bulalım.

ÖRNEK:  Öklid Algoritmasını kullanarak 156 ve 65 sayılarının EBOB'unu hesaplayıp, EBOB(156,65)=x.156+y.65 olacak şekilde x ve y tamsayılarını bulunuz.

ÇÖZÜM: Yukarıdaki örnekte olduğu gibi ardarda sırasıyla bölme işlemi yapılırsa kalanın 0 olduğu son bölme işleminde bölen sayısı 13 olduğundan EBOB(156,65)=13 olarak bulunur.Sorunun ikinci aşamasında ise bu sayıların bölüm algoritmasına göre yazımını yapacağız. Bunun için Bir bölme işleminde Bölünen sayı=Bölen Sayı . Bölüm + Kalan olarak yazıldığından bütün yaptığımız bölümlerde bunu kullanacağız.

156= 65*2+26

65=26*2+13

26=13*2+0

Daha sonra her bir algoritma için kalanları diğerlerinin cinsinden çekerek yazalım. Sıfır kalanın olduğu bölme işleminden başlayarak en baştaki bölme işlemine kadar bunu yazalım.

0=26-13*2

13=65-26*2

26=156-65*2

EBOB=13 olduğundan 13ün eşitliğinde bulduğumuz ifadeleri yazalım.

13=65-26*2

13=65-(156-65*2)*2 Bu kısımı içeriye dağıtarak düzenleyelim.

13=65-(2*156-4*65)

13=65 - 2*156 + 4*65

13=5*65-2*156 bulunur. EBOB(156,65)=x.156+y.65 sorusuna göre x=-2 ve y=5 bulunmuş olur.

ÖRNEK:  Öklid Algoritmasını kullanarak 1029 ve 1071 sayılarının EBOB'unu hesaplayıp, EBOB(1029,1071)=x.1029+y.1071 olacak şekilde x ve y tamsayılarını bulunuz.

ÇÖZÜM: Aynı şekilde ardarda bölme işlemleri yapıyoruz. Yapılan son bölme işleminde kalanın sıfır olduğu durumda bölen sayısı 21 olduğundan EBOB(1029,1071)=21 olarak bulunur. 

Bu aşamadan sonra sorunun ikinci bölümü için yukarıda yaptığımız gibi, tekrar her bir bölmedeki kalanları diğer bölünen ve bölenlerin cinsinden yazalım.

0=42-2*21

21=1029-42*24 (EBOB'un olduğu kalan bizim için önemli)

42=1071-1*1029

Bu aşamada kalanların yerine değerlerini yazarak işlemleri en sade hale getiriyoruz. 42'nin karşılığını bir üst eşitlikte yazıyoruz.

21=1029-(1071-1*1029)*24

21=1029-24*1071+24*1029

21=25*1029-24*1071 bulunmuş olur. Bu son eşitlikte EBOB(1029,1071)=21  olduğundan EBOB(1029,1071)=x.1029+y.1071 sayıları karşılıklı olarak  x=1029 ve y=-24 olarak bulunur.

ÇÖZÜM:Verilen örneğin çözümünde yine ardışık bölme işlemlerinden yararlanacağız. 253 sayısı 110 ile bölünerek bölmeye başlanır ve en son sıfır kalanını verene kadar bölmeye devam edilir sıfır kalanın olduğu bölme işleminde en son bölen sayı 11 olduğundan bu iki sayının ebobu 11 olarak bulunur ki bu durumda en son bölüm değeri de soruda m değerine eşit olur. 

33=253-2*110

11=110-3*33

Buradan 33 yerine eşitlik değeri yazılırsa;

11=110-3*(253-2*110)

11=110-3*253+6*110

11=7*110-3*253 bulunur. Son durumda x=-3 ve y=7 olur ki x+y=4 olabilir.

---

YUKARIDA ANLATTIKLARIMIZA BENZER ÖRNEKLERİN ÇÖZÜMÜ İÇİN SİZLER DE AŞAĞIDAKİ SORULARI KENDİNİZ HESAPLAYINIZ. 

---

<<<***>>>  k, bir tamsayı olmak üzere; ** EBOB(A,B)=EBOB(A, A-B.k)       ** EBOB(A,B)=EBOB(A, A-B)  ** EBOB(A,B)=EBOB(A, A+B) şeklinde yukarıda konu anlatımında verilen özelliğin kullanımı için kapsamlı bir örnek vererek konuyu kapatalım. Çok Büyük üslü sayılar şeklinde verilen iki sayı için EBOB bulunurken bu kuralın iyi bilinmesi yararlı olacaktır. Üslü biçimde verilen aşağıdaki örnekte iki sayının EBOB'u, bu iki sayıdan küçük olan ile diğer büyük sayının toplamından veya farkından oluşacak EBOB değerine eşittir. Bu şekilde en sade hale gelinceye kadar devam edilirse en sonunda genellikle aralarında asal olması durumu ortaya çıkar ki bu durumda EBOB'ları 1'e eşit olur. Pratik bir yol olarak üslü biçimde verilen aynı sayının kuvvetlerinin +1 fazlalarının veya -1  eksikliklerinin birlikte (2^m+1  ve 2ⁿ+1 gibi sayılar için ebob hesabında) EBOB'u bulunurken sayıların kuvvetlerine bakılır. Eğer kuvvetler (m ve n) kendi aralarında asal ise bu durumda bu oluşacak sayılar da kendi aralarında asal olur ve EBOB'ları da  bu durumda 1'e eşit olur. Aşağıdaki çözümü ayrıntılı bir şekilde verilen örneği dikkatlice inceleyiniz. (El yazısı çözüm için Mat.Öğrt. Necdet Kirpi'ye teşekkürler)