Bölünebilme ve Ebob

Bu bölümde herkesin ilkokulda öğrendiği bölme işleminin bazı özellikleri ve bu özelliklerin sonuçları üzerine düşüneceğiz. Bu özelliklerden bazı yeni notasyonlar üretip bunlarla işlem yapacağız. Ama öncelikle bölme işleminin sezgisel olarak ne ifade ettiğini hatırlayalım. Bölme işlemindeki temel motivasyon bütünü parçalara ayırma isteğidir. Sayıların ne olduğuyla ilgili bir sezgiye sahip bir mağara adamı düşünelim. Yani on tane elması varsa bu elmalardan her birini bir el parmağıyla eşleştirmeyi bilen bir mağara adamı. Bu mağara adamının ailesi beş kişiden oluşsun. Bu elli tane elmayı eşleştirebilecek el parmakları demek. Şanslı mağara adamı! Ya üç kişilik ailesi olsaydı? Otuzla yetinmek zorunda kalacaktı.Belki de biraz akıllıysa ailenin ilk iki üyesinin parmaklarını elmalarla eşleştirip sonuncu üyenin parmaklarını ilk iki üyenin parmaklarının tamamen elmalarla eşleştirilme işleminin kaç kez tekrar ettiğini saymak için kullanabilirdi. Böylece iki yüz elmanın ne olduğunu sezgisel olarak anlayabilecekti. Bizim anladığımız dile iki yüz tane elmaya sahip olmak onun için çocuğunun parmakları kadar kere, eşinin ve kendisinin bütün parmaklarıyla eşleştirebilecekleri elmalarının var olması demekti.Mağara adamı daha akıllıca davranıp iki yüzden de fazla elmanın ne anlama geldiğini kavrayabilir mi ? Üzerine düşünün. Bu sorunun cevabının teknik olarak evet olması gerekiyor. Çünkü zamanı ileriye sararsak o mağara adamları, elmalara ihtiyaç dahi duymadan sayıları zihinsel olarak tanımlayabilen biz modern insanlara dönüştü. Ancak burda tümdengelimsel düşünmeyi bir kenara bırakıp daha ilkel yollarla düşünmeye devam edelim. Adam kendi parmaklarıyla elmaları eşleştirsin. Eşi ise adamın parmaklarının hepsi eşleştirildikçe bir parmağını kaldırsın. Eşi bir parmağını kaldırdıkça adam başa dönsün. Çocuğu ise annesinin parmaklarının tamamı havadayken bir parmağını kaldırsın ve annesi başa dönsün. Bu yöntemle bin elmanın ne olduğunu anlayabilirler. Yani bizlerin bin elma dediği şey bu adam için çocuğunun parmakları kere, eşinin parmakları kere kendi parmağı kadar elma demektir. Bu ailenin üç yüz elli sekiz olması olsun. Son bahsettiğimiz yöntemle elmaları saymaya çalışsınlar. Çocuğun bir parmağının havada olması, annenin on parmağının tamamının bir kere havada olmuş olması demek. Bu da adamın on parmağının on kere havada olması. Dolayısıyla çocuğun bir parmağının havada olması en azından yüz elmaya sahip olduklarının garantisi. Aynı yapıda düşünürsek annenin bir parmağının havada olması en azından on elmaya sahip olduklarının garantisi. Bu durumda üç yüz elli sekiz tane elmayı saymayı tamamladıklarında çocuğun üç parmağı havada olmalı. Çünkü üç yüzün içinde en fazla üç tane yüzlük grup oluşturulabilir. Annenin ise beş parmağı havada olmalı. Çünkü elli sekiz elma içinde en fazla beş tane onluk grubu oluşturulabilir. Babanın da tahmin edileceği üzere sekiz parmağı havada olmalı. Bu aile artık o kadar da ilkel sayılmaz. Bizim basamaklara ayırmak dediğimiz şeyi keşfettiler. Çocuğun havada olan parmakları yüzler basamağını temsil ediyor. Annenin havada olan parmakları onlar basamağını, babanınki ise birler basamağını. Bu basamaklara ayırma işlemini onluk sistem üzerinde yaptık. Takdir edersiniz ki, bu ailedekilerin elleri on parmaklı. Şimdi tüm bu elmalardan ve parmaklardan kurtulup bu basamaklara ayırma işlemini sembolik olarak yapalım.

Bu kadar derin bir anlayışa sahip olan mağara adamının parçalayamayacağı bir bütün yoktur artık :) Yukarıdaki akıl yürütmemizde mağara adamına elmaları yüzlük ve onluk parçalara ayırttırmayı becerdik. Şimdi daha kolay bir problemi çözdürelim mağara adamımıza. Üç kişilik ailesi için yirmi dört adet toplam elması olsun. Demokrat mağara ailesi, elmaları eşit bölüşmek istiyorsa her birine kaç elma düşer. Ailenin her üyesi sırayla bir elma alıp bir parmağını kaldırsın. Bütün elmalar bittiğinde ailenin her üyesinin toplamda sekiz parmağı havada olacak. Eğer toplamda yirmi beş tane elma olsaydı, ailenin başı büyük dertte olacaktı. Ama yirmi dört olduğu için hepsinin aynı parmakları havada. Büyük şans. Sezgisel olarak mağara adamının yirmi dört elmayı üç kişiye aynı parmakları havada olacak şekilde üleştirmesi, formel olarak şuna tekabül eder:Yirmi dört üçe bölünür. Ya da üç yirmi dördü böler. Bazen böler ifadesi yerine tam böler ifadesi kullanılır. Ama bu anlamsızdır. Bu kitapta bundan sonra böler olarak ifade edeceğimiz olgu tam bölmeye denk düşer. Zaten bölme işlemi tamamlandığında kalan varsa o zaman böler demeyiz. Örneğin yirmi beş elmaları olsaydı bir tane elma artacağı için yirmi beş üçe bölünemez ya da üç yirmi beşi bölemez diyecektik.

Yukarıdaki örnekte yirmi dört a sayısı, üç b sayısı iken sekiz d sayısı olmuş oluyor. Örneğin a sayısı on iki iken b sayısı iki olsun. d şartını sağlayan altı sayısı var olduğu için on iki ikiye bölünür. Elbette ki bunlar küçük sayılar olduğu için bu işlemleri kısa sürede yapıp sonuca ulaşabiliriz. Ancak 192850 ve 123456 gibi sayıların ikiye veya üçe tam bölünüp bölünemeyeceğini işlem yaparak anlamaya çalışmak hem akılsızca olurdu hem de tembel insanların yeltenmeyeceği bir iş olurdu. İşte bu yüzden bazı sayılara bölünebilme ile ilgili kurallar geliştireceğiz. Ancak önce kanıtlamamız gereken ufak bir önsav var.

<

Kanıt: Önce önermenin ne dediğini anlamaya çalışalım. a sayısı beş olsun. b ve c sayıları ise sırasıyla yirmi ve yirmi beş olsun.

Şimdi r₁ > rolmak üzere b = q₁a + r₁ ve 0 ≤ r₁ < a şartlarını sağlayan bir (q₁, r₁) sayı çifti olduğunu varsayalım. Amacımız çelişki yöntemiyle r₁ = r eşitliğini göstermek olacak. Kolayca görülebileceği üzere 0 ≤ r₁ − r < a eşitsizliği sağlanır. Öte yandan r₁ − r = a(q − q₁) eşitliği söz konusu. Bu eşitlikte sağ taraf a ile bölünebildiği için sol taraf da a ile bölünmek durumunda. Başka bir deyişle a ∣ (r₁ − r). Ancak r₁ − r sayısı a sayısından küçük bir sayı. Pozitif bir tam sayının kendinden küçük bir pozitif tam sayıyı bölmesi (bir önceki teoremden ötürü) imkansız olduğu için r₁ − r sayısının sıfıra eşit olması gerektiğini dolayısıyla r₁ = r eşitliğinin sağlandığını göstermiş olduk. q₁ ve q sayıları da r ve r₁ sayıları tarafıdan belirlendikleri için (r, q) ikilisinin (r₁, q₁) ikilisine eşit olduğunu; yani b = qa + r denklemini ve 0 ≤ r < a koşulunu sağlayana q ve r tam sayılarının biricik olması gerektiğini göstermiş olduk.

Bu teoremin isimlendirilmesiyle ilgili dikkatinizi çeken bir şey var mı? Algoritmalar, bir sonuç elde edebilmek için uygulanan matematiksel süreçler veya metodlardır.(Daha fazla bilgi için 16. Bölüme bakınız.) Bölme Algoritması diye adlandırdığımız bu teorem bize gerçekten bir algoritma sunuyor mu? Teoremin iddiasında geçen "öyle biricik q ve r tam sayıları bulabiliriz ki" ifadesi bu sayıları bulmak için bir algoritma sunmaktansa var olduklarını temin ediyor. Ancak ispatımızın ilk paragrafında kullandığımız yöntem bu sayıları nasıl bulacağımıza dair ipucu veriyor. Her ne kadar teoremimiz tam olarak bir algoritma olmasa da, hem geleneksel olarak böyle adlandırıldığı için hem de ispatında bir algoritma kullandığımız için bu teoremi bölme algoritması olarak adlandırdık.

Şimdi cep telefonumuzun veya bilgisayarımızın hesap makinesi yardımıyla q ve r sayılarını nasıl hesaplayabileceğimiz üzerine düşünelim. Örneğin b=953 ve a=433 olsun. Eğer bir hesap makinesi yardımıyla b’yi a’ya bölersek ekranda 2.2 gibi bir sonuç görürüz. Makinemiz gelişmiş bir makineyse eğer, virgülden sonraki basamakların sayısı daha da artabilir. Yine de ekranda göreceğimiz bu sonuç kesin sonuç değil yaklaşık bir değer olacaktır. Ne var ki bu değeri kullanarak bölme algoritmasında adı geçen q ve r sayılarını tespit edebiliriz. Örneğimizde q sayısı ikiye eşit olmalıdır. Daha genel haliyle q sayısı $\frac{b}{a}$’yı aşmayan en küçük tam sayıdır ve $\lfloor \frac{b}{a} \rfloor$ şeklinde gösterilir. Bu fonksiyonu tam değer fonksiyonu veya aşağı yuvarlama fonksiyonu olarak adlandırabiliriz. Bu fonksiyon genel haliyle şunu söyler: ⌊x⌋, ⌊x⌋ ≤ x < ⌊x + 1⌋ şartını sağlayan biricik tam sayıdır. q sayısının değerinin 2 olduğunu gördükten sonra r sayısını bulmak için bölme algoritmasını kullanabilirz. b=953 ve a=433 sayılarını b − qa = r eşitliğinde yerine koyarsak r = 953 − 2.433 = 87 elde ederiz. Görüleceği üzere 0 ≤ 87 < 433 eşitsizliği sağlanıyor ve 87, b − qa şeklinde ifade edilebilen en küçük negatif olmayan sayı. Dolayısıyla yaptığımız işlem isabetli ve q=2 ve r=87 bölme algoritmamızı sağlar.

Lise eğitimi almış olan hemen hemen herkes verilen iki sayının en büyük ortak böleninin nasıl hesaplanacağına dair fikir sahibidir. Sayıları asal çarpanlarına ayırmak suretiyle bu çarpanlar arasında ortak görülen sayıların en büyük üslü olanlarını alıp birbiriyle çarparak en büyük ortak böleni hesaplayabiliriz. Ancak bu çok büyük sayılar söz konusu olduğunda efektif bir yol olmayabilir. Söz gelimi 42823 ve 6409 gibi iki sayı verildiğinde bu sayıların en büyük ortak bölenini yukarıda bahsedildiği şekliyle hesaplamaya kalkışmak zihinsel bir işkenceye dönüşebilir. Matematik söz konusu olduğunda zihinsel işkenceden ziyade zihinsel haz ve estetik doyumlarla karşılaşmak daha olasıdır. Şimdi Öklid’in Elemanlar adlı kitabında açıkladığı EBOB hesaplamaya yönelik estetik ve efektif bir yöntemi inceleyeceğiz. Ancak öncesinde küçük hazırlıklar yapmamız gerekiyor.

İspat: Eğer b ve a’nın ortak bölenlerinin a ve r’nin ortak bölenleriyle aynı olduğunu gösterebilirsek, EBOB(b, a) = EBOB(a, r) eşitliğini kanıtlamış oluruz. Çünkü ortak bölenlerin aynı olması en büyük ortak bölenlerin de aynı olmasına sebebiyet verir.O halde amacımız b ve a’nın ortak bölenlerinin a ve r’nin ortak bölenleriyle aynı olduğunu göstermek olmalı.Başka bir deyişle aynı anda b’yi ve a’yı bölen herhangi bir tam sayının r’yi de bölmesi gerektiğini veya aynı anda a’yi ve r’yi bölen herhangi bir tam sayının b’yi de bölmesi gerektiğini göstermek.

Öncelikle bir d sayısının a ve b tam sayılarının ortak böleni olduğunu varsayalım. Önsavımızda belirtilen eşitlikte r’yi yalnız bırakırsak r = b − qa elde ederiz. Ancak d sayısı hem a’yı hem de b’yi böldüğü için b − qa’yı da böler.(Teorem ? Bölüm 7) Dolayısıyla a ve b’nin ortak bölenlerinin r’yi de böldüğünü göstermiş olduk.

Şimdi herhangi bir d sayısının a ve r tam sayılarının ortak böleni olduğunu varsayalım. d sayısı qa + r sayısını da böler. (Teorem ? Bölüm 7) b = qa + r olduğu için d sayısının b’nin de bir böleni olduğunu söyleyebiliriz.

Dolayısıyla a ve b’nin ortak bölenlerinin a ve r’nin ortak bölenleriyle arzuladığımız gibi aynı olduğu sonucuna ulaşabiliriz. Bu da bize a,b,q ve r tam sayılar olmak üzere b = qa + r ise EBOB(b, a) = EBOB(a, r) eşitliğinin sağlandığını kanıtlar.

Artık elimizde güçlü bir araç var. Bu aracı doğru kullanabilirsek 42823 ile 6409 sayılarının en büyük ortak bölenlerini hesaplamak artık zihinsel bir işkence olmaktan çıkabilir. Öklid’in yaptığı şey de bu aracı doğru kullanmaktan ibaretti. Teoremimizi yazmadan önce algoritmanın nasıl işleyeceğine dair bir şema çizelim. Elimizde 42823 ve 6409 sayıları ile önsav ? var. Önsavdaki ilk cümle size tanıdık geldi mi? Buradaki eşitlik bölme algoritmasında sözü geçen eşitlikten başkası değil. O halde 42823 ve 6409 sayılarına bölme algoritmasını uygulayarak bu iki sayının EBOB’unu bulma problemini daha küçük iki sayının EBOB’unu bulma problemine dönüştürebiliriz. Şimdi söylediklerimize işleme dökme zamanı:

Sayılarımıza bölme algoritmasını uygulayarak q ve r tam sayılarını belirledik. Artık önsavdan dolayı EBOB(42823,6409)’u hesaplamak EBOB(6409,4369)’u hesaplamaya denk bir sorun haline geldi.Şimdi işlemimizi bir adım ileriye götürebiliriz. Yani 6409 ve 4369’a bölme algoritmasını uygulayarak problemimizi daha küçük sayılar için EBOB bulmaya indirgeyebiliriz:

Bu süreci nereye kadar devam ettirmemiz gerekir? Elbetteki r değeri sıfır olana kadar. Bu durumda son denklemde b′ = qr′ elde ederiz. Ve yapmamız gereken şey EBOB(b’,r’)’ı hesaplamak olur. Bu da r’ sayısına eşittir.Yani sondan bir önceki denklemin kalanına. Şimdi bu söylediklerimizi kağıt üzerinde görelim:

Görüleceği üzere elimizdeki aleti akıllıca kullanarak EBOB(42823,6409) gibi zor bir problemi EBOB(289,17) gibi kolay bir probleme dönüştürdük. İşte Öklid Algoritması olarak adlandırdığımız teorem bize en büyük ortak bölen hesaplaması yaparken bu kolaylığı sağlıyor.

Diyofant Denklemleri

Bu bölümde iki bilinmeyenli lineer Diyofant denklemlerini araştıracağız. Cebirin babası olarak da anılan Diyofant İskenderiye’li bir matematikçidir. En önemli eseri Aritmetika’da cebirsel denklemlerin çözümleri ve sayı teorisi üzerine çalışmıştır. Kendi adıyla anılan Diyofant denklemlerinde ise, çoğunlukla 2 veya daha fazla bilinmeyeden oluşan tam katsayılı denklemlerin tam sayı çözümleriyle ilgilenilir. Bu kitabı okuyan herkes muhakkak Pisagor denklemiyle haşır neşir olmuştur. x² + y² = z² şeklinde ifade edilebilecek Diyofant denklemine Pisagor üçlüleri çözüm sağlar. Genel olarak Diyofant denklemleriyle uğraşırken üç ana uğraşımız olur. İlk uğraşımız verilen bir Diyofant denklemine çözüm bulabilir miyiz sorusudur. İkinci uğraşımız eğer çözüm bulabiliyorsak, denklemin çözümleri sonlu tane midir yoksa sonsuz çözümü mü vardır sorusudur. Üçüncü uğraşımız ise denklemimizin çözümleri varsa bu çözümleri nasıl tespit edebiliriz sorusudur. Bu bölümde en basit Diyofant denklemlerinden biri olan iki değişkenli lineer Diyofant denklemleriyle uğraşacağız. Bu yolda Bezout Teoremi adını vereceğimiz teorem en büyük yardımcılarımızdan biri olacak. Ancak bu teoremden önce Öklid Algoritması yardımıyla 252x + 198y = 18 denklemine çözüm bulmaya çalışalım.

Örnek: 252x + 198y = 18 denklemini sağlayan x ve y bulalım.

Çözüm: Öncelikle Öklid algoritması yardımıyla 252 ve 198 sayılarının en büyük ortak bölenini hesaplayalım.

EBOB(252,198)=18 olduğunu görmüş olduk. Şimdi üçüncü denklem sayesinde 18’i 54 ve 36’nın lineer kombinasyonu olarak yazabiliriz. 18 = 1.54 − 1.36 Öte yandan ikinci denklem sayesinde 36’yı 54 ve 198’in lineer kombinasyonu olarak yazabiliriz. 36 = 1.198 − 3.54 Şimdi (?.?)’yı (?.?)’da yerine yazarsak 18 = 1.54 − 1.198 + 3.54 = −1.198 + 4.54 elde ederiz. Son olarak birinci denklemi kullanarak 54’ü 252 ve 198’in lineer kombinasyonu olarak yazalım. 54 = 1.252 − 1.198 Son olarak (?.?)’yı (?.?)’da yerine yazalım. 18 = −1.198 + 4.(1.252 − 1.198) = 4.252 − 5.198 Gördüğümüz üzere (4,-5) sayı çifti 252x + 198y=18 denklemini sağlamış oldu.

İspat: EBOB(a,b)=d olsun. d’nin c’yi böldüğünü varsayalım. O halde öyle bir n tam sayısı bulabiliriz ki c=dn sağlanır. Bézout teoremi sayesinde d = ax′ + by′ şartını sağlayan t ve s tam sayıları bulabiliriz. Şimdi d = at + bs denkleminde her tarafı n ile çarpalım. Bu durumda dn = c = atn + bsn olur. Dolayısıyla x=tn ve y=sn için ax + by = c denklemi sağlanır.

Diğer taraftan ax + by = c denklemini sağlayan bir çözüm olduğunu varsayalım. EBOB(a,b)=d olduğu için d, a ve b’nin ortak bölenidir. Dolayısıyla d, ax+by’yi böler. ax+by=c olduğu için d=EBOB(a,b), arzu edildiği gibi c’yi böler.Kanıtımız tamamlanmıştır.

İspat: Bézout Teoremi sayesinde öyle x₀, y₀, x₁, y₁ tam sayıları bulabiliriz ki, ax₀ + my₀ = 1 ve bx₁ + my₁ = 1 eşitlikleri sağlanır. Bu eşitliklerde ax₀ ve bx₁i yalnız bırakırsak (ax₀.)(bx₁) = (1 − my₀)(1 − my₁) = 1 − my₀ − m_y1 + my₀my₂elde ederiz. y₂ = y₀ + y₁ − my₀y₁ olsun. Bu durumda abx₀x₁ = 1 − my₂ olur. Dolayısıyla abx₀x₁ + my₂ = 1 denklemini elde ederiz. Bu durumda ab ve m’nin herhangi bir ortak böleni 1’i de bölmek zorundadır.(Teorem?) Başka bir deyişle ab ve m’nin en büyük ortak böleni 1’dir.