Ana içerik

Öklid Algoritması

İki A ve B tam sayısının Ortak Bölenlerinin En Büyüğünün (OBEB), A ve B'yi bölen en büyük tam sayı olduğunu hatırlayalım.

Öklid Algoritması, iki tam sayının OBEB'ini hızlıca bulmak için kullanılan bir yöntemdir.

Algoritma

OBEB(A,B)'nin bulunması için Öklid Algoritması şu şekildedir:

Eğer A=0 ise, OBEB(0,B)=B olacağı için OBEB(A,B)=B olur ve bu noktada durabiliriz.
Eğer B=0 ise, OBEB(A,0)=A olacağı için OBEB(A,B)=A olur ve bu noktada durabiliriz.
A sayısını bölüm ve kalan formunda yazın (A=B⋅Q+R)
OBEB(A,B)=OBEB(B,R) olduğu için, OBEB(B,R)'yi Öklid Algoritmasını kullanarak bulun

Örnek:

270 ve 192'nin OBEB'ini bulun

A=270, B=192
A ≠0
B ≠0
Bölme yapılarak, bölüm 270/192 = 1 ve kalan 78 olarak bulunr. Bu işlemi 270 = 192 * 1 +78 şeklinde de yazabiliriz
OBEB(270,192)=OBEB(192,78) olduğu için OBEB(192,78)'i bulun

A=192, B=78

A ≠0
B ≠0
Bölme yaparak, bölüm 192/78 = 2 ve kalan 36 olarak bulun. Bunu şöyle yazabiliriz:
192 = 78 * 2 + 36
OBEB(192,78)=OBEB(78,36) olduğu için, OBEB(78,36)'yı bulun

A=78, B=36

A ≠0
B ≠0
Bölme yapılarak, bölüm 78/36 = 2 ve kalan 6 olarak bulun. Bunu şöyle yazabiliriz:
78 = 36 * 2 + 6
OBEB(78,36)=OBEB(36,6) olduğu için, OBEB(36,6)'yı bulun

A=36, B=6

A ≠0
B ≠0
Bölme yapılarak, bölüm 36/6 = 6 ve kalan 0 olarak bulunur. Bunu şöyle yazabiliriz:
36 = 6 * 6 + 0
OBEB(36,6)=OBEB(6,0) olduğu için, OBEB(6,0)'yı bulun

A=6, B=0

A ≠0
B =0, OBEB(6,0)=6

Böylece şunu göstermiş olduk:

OBEB(270,192) = OBEB(192,78) = OBEB(78,36) = OBEB(36,6) = OBEB(6,0) = 6

OBEB(270,192) = 6

Öklid Algoritmasını Anlamak

Öklid Algoritmasını incelersek, aşağıdaki özellikleri kullandığını görürüz:

EBOB(A,0) = A
EBOB(0,B) = B
Eğer A = B⋅Q + R ve B≠0 ise bu durumda OBEB(A,B) = OBEB(B,R) burada Q bir tam sayıdır, R 0 ve B-1 arasında bir tam sayıdır

İlk iki özellik, iki sayıdan birinin 0 olması durumunda OBEB'i bulmamızı sağlar. Üçüncü özellik ise, daha büyük ve zor sayıları alıp, daha küçük, basit sayılara indirgeyerek problemi çözmemizi sağlar.

Öklid Algoritması, üçüncü özelliği sayesinde problemin hızla ve ilk iki özellik kullanılarak çözülebilecek hale gelene kadar daha basit problemlere dönüştürülerek çözülmesini sağlar.

Bu özelliklerin neden işe yaradığını onları ispatlayarak anlayabiliriz.

OBEB(A,0)=A özelliğinin ispatı şu şekildedir:

A'yı kalansız bölebilecek en büyük tam sayı A'nın kendisidir.
Herhangi bir C tam sayısı için C⋅ 0 = 0 olduğu için, bütün tam sayılar 0'ı kalansız bölebilir. Öyleyse A tam sayısının da 0'ı kalansız bölebileceği sonucuna varabiliriz.
A ve 0'ı bölen en büyük tam sayı, A tam sayısıdır.

OBEB(0,B)=B özelliğinin ispatı da hemen hemen aynıdır. (İspat aynıdır, ancak A yerine B koyarız).

OBEB(A,B)=OBEB(B,R) olduğunu ispatlayabilmemiz için, önce OBEB(A,B)=OBEB(B,A-B) olduğunu göstermemiz gereklidir.

A-B=C koşuluyla A,B ve C diye üç tam sayımız olduğunu varsayalım.

OBEB(A,B)'nin C'yi kalansız böldüğünün ispatı

Tanıma göre OBEB(A,B)'nin A'yı kalansız böldüğünü biliyoruz. Bu durumda, A tam sayısı OBEB(A,B)'nin bir katı olmalıdır. Yani, X⋅OBEB(A,B)=A, burada X bir tam sayıdır

Gene tanımı nedeniyle OBEB(A,B)'nin B'yi kalansız böldüğünü biliyoruz. Bu durumda, B tam sayısı OBEB(A,B)'nin bir katı olmalıdır. Yani, Y⋅OBEB(A,B)=B, burada Y bir tam sayıdır

A-B=C bize şunu verir:

X⋅OBEB(A,B) - Y⋅OBEB(A,B) = C
(X - Y)⋅OBEB(A,B) = C

Böylelikle, OBEB(A,B)'nin C'yi kalansız böldüğünü görmüş oluyoruz.

Bu ispatın bir örneği, aşağıdaki şeklin sol kısmında gösterilmiştir:

OBEB(B,C)'nin A'yı kalansız böldüğünün ispatı

Tanıma göre, OBEB(B,C)'nin B'yı kalansız böldüğünü biliyoruz. Bu durumda, B tam sayısı OBEB(B,C)'nin bir katı olmalıdır. Yani, M⋅OBEB(B,C)=B, burada M bir tam sayıdır

Tanıma göre OBEB(B,C)'nin C'yi kalansız böldüğünü biliyoruz. Bu durumda, C tam sayısı OBEB(B,C)'nin bir katı olmalıdır. Yani, N⋅GCD(B,C)=C, burada N bir tam sayıdır

A-B=C bize şunu verir:

B+C=A
M⋅OBEB(B,C) + N⋅OBEB(B,C) = A
(M + N)⋅OBEB(B,C) = A

Böylelikle, OBEB(B,C)'nin A'yı kalansız böldüğünü görmüş oluyoruz.

Bu ispatın bir örneği, aşağıdaki şekilde gösterilmiştir:

OBEB(A,B) = OBEB(A,A-B) olduğunun ispatı

Tanımı gereği, OBEB(A,B), B tam sayısını kalansız böler.
OBEB(A,B)'nin C tam sayısını kalansız böldüğünü zaten ispatlamıştık.
OBEB(A,B) hem B'yi, hem de C'yi kalansız böldüğü için, B ve C'nin ortak bölenlerinden biridir.

OBEB(A,B), OBEB(B,C)'den küçük veya OBEB(B,C)'ye eşit olmalıdır; çünkü OBEB(B,C), B ve C tam sayılarının “en büyük” ortak bölenidir.

Tanımı gereği, OBEB(B,C), B tam sayısını kalansız böler.
OBEB(B,C)'nin A'yı kalansız böldüğünü zaten ispatlamıştık.
OBEB(B,C) hem A'yı, hem de B'yi kalansız böldüğü için, A ve B'nin ortak bölenlerinden biridir.

OBEB(B,C), OBEB(A,B)'den küçük veya OBEB(A,B)'ye eşit olmalıdır; çünkü OBEB(A,B), A ve B tam sayılarının “en büyük” ortak bölenidir.

OBEB(A,B)≤OBEB(B,C) ve OBEB(B,C)≤OBEB(A,B) özellikleri sayesinde, şu sonuca varabiliriz:

OBEB(A,B)=OBEB(B,C)

Bu, şuna eşittir:

OBEB(A,B)=OBEB(B,A-B)

Bu ispatın bir örneği, aşağıdaki şeklin sağ kısmında gösterilmiştir.

OBEB(A,B) = OBEB(B,R) olduğunun ispatı

OBEB(A,B)=OBEB(B,A-B) olduğunu ispatladık

Terimlerin sırası önemli olmadığından, OBEB(A,B)=OBEB(A-B,B) diyebiliriz

OBEB(A,B)=OBEB(A-B,B) özelliğini tekrar tekrar uygulayarak şu sonuca ulaşabiliriz:

OBEB(A,B)=OBEB(A-B,B)=OBEB(A-2B,B)=OBEB(A-3B,B)=...=OBEB(A-Q⋅B,B)

Ancak A= B⋅Q + R olduğundan, A-Q⋅B = R olur