Yazan : Şadi Evren ŞEKER
Bilgisayar bilimleri de dahil olmak üzere pek çok matematik temelli bilim için önemli olan denklemlerdir. Milattan önce 3. yüzyılda İskenderiye’de yaşamış olup bugün için oldukça önemli olan denklemleri bırakmıştır. Aynı zamanda Fermat’ın son denklemi olarak geçen denkleme de öncülük etmiştir.
Bilgisayar bilimleri açısından özellikle tam sayılar üzerine kurulu olan şifreleme (kriptoloji, cryptography) veya çizge kuramı (graph theory) gibi konularda önemli bir yere sahiptir.
Diyofantus basitçe aşağıdaki şekilde verilen denklemlerin çözümünü aramıştır.
A= x + y
B = x 2 + y 2
C = x 3 + y 3
Diğer bir deyişle Diyofantus’in bulmaya çalıştığı şey, birinci ikinci veya n’inci dereceden ikililerin toplamı sonucunda çıkan değerdir yani bu denklemin çözüm kümesidir.
Örneğin yukarıdaki denklemlerden ilkini ele alalım:
A= x + y
şeklinde verilen denklem aslında birinci derece olması hasebiyle, doğrusal bir bağlantıdır (linear equation). Bu denkleme çözüm üretmesi açısından denklemi geliştirirsek:
ax + by = c şeklindeki bir denklem için çözüm kümesinin
(a,b) | c şeklinde tam böler olmaları gerektiğini söyleyebiliriz.
Farklı bir örnek olarak (9,100) ikilisini alalım. Bu iki sayı a ralarında asaldır (relatively prime) ( en büyük ortak böleni 1’dir). Bu durumda aşağıdaki denklem için:
9x + 100y = 1
denklemi sağlayan x ve y değerleri bulunabilir.
Örneğin x = -11 ve y = 1 veya x = 89 ve y = -8 gibi sonuçlar denklemi sağlar. Aslında modüler aritmetik ile düşünüldüğünde bu denklemin sonsuz sayıda çözümü olduğunu söyleyebiliriz.
Diophantine denklemlerini çözerken sonsuz sayıdaki çözümü bir denklem ile göstermek daha akılcı olabilir.
Örneğin aşağıdaki denklemi çözmek isteyelim:
6x + 9y = 21
(6,9) | 21 koşulu sağlanmaktadır (6 ile 9’un en büyük ortak böleni 3’tür ve 3|21 durumu sağlanmaktadır). Bu durumda hızlı bir çözüm ile +7 ve -7 değerleri için aşağıdaki denklemler yazılabilir:
x = 3k – 7
y = -2k + 7
Örneğin k = 5 için x = 8 ve y = -3 çözümleri bulunur.
Yukarıdaki özel durumu genelleştirecek olursak aşağıdaki çözüm yöntemini geliştirebiliriz:
(a,b) = d | c şartını sağlamak üzere verilen bir
ax + by = c denklemi için
Çözümleri yazılabilir. Buradaki k tam sayı olması şartı bulunur.
Denklemde bulunan x0 ve y0 değerleri ise herhangi bir çözümde elde edilen sonuçtur. Nitekim modüler aritmetik bir tekrarlı grup oluşturmakta (linear congurent) ve yukarıdaki denklemlerde buna işaret etmektedir.
Yukarıdaki yazdığımız denklemleri kullanarak örneğimizi tekrar çözmeye çalışalım:
6x + 9y = 21
(6,9) = 3 | 21 olduğuna göre
a=6, b=9, c=21 ve d=3 olarak kabul ediyoruz ve denklemin bir ilk çözümünü buluyoruz. Örneğin x0 = -7 ve y0 = 7
Buna göre denklem sistemimiz aşağıdaki şekilde çözülmüş olur:
yukarıdaki iki denklemin sadeleştirilmiş hali ise zaten çözdüğümüz
x = 3k – 7
y = -2k + 7
denklemlerini vermektedir.
Yukarıdaki durumu çözen bir kod yazmaya çalışalım:
Öncelikle, verilen sayılar için d= obeb(a,b) değerini hesaplıyor ve ardından şayet c ile aralarında asal değillerse (relatively prime), x0 ve y0 değerlerini hesaplıyoruz. Sonuçta bulunan değerleri bir denklem şeklinde ekrana bastırıyoruz.
Yukarıdaki kodda belki biraz zor olan kısım ilk değerlerin hesaplanmasıdır. Burada nümerik bir yöntem izleyerek bütün ihtimalleri x0 = 0 ve y0 = 0 durumundan başlatarak hesaplatıyoruz. Bu işlemler için kullanılan yardımcı fonksiyonlar aşağıdaki şekilde kodlanmıştır.
Yukarıdaki kodun çıktısı aşağıda verilmiştir:
Gelelim çoklu denklemlere. Çoklu denklemler için öncelikle meşhur olmuş maymun ve hindistan cevizi problemine (monkey and coconut problem) bir bakalım:
“batan bir gemiden kurtulan n adam ve bir maymun ıssız bir adaya çıkarlar. Adamlar ormandaki ağaçlardan hindistan cevizi toplayıp bir köşeye yığarlar ve sonra uykuya çekilirler. İçlerinden birisi gece uyanıp gizlice cevizleri n’e böler artan bir tanesini maymuna verdikten sonra kendi payını alır ve hiçbir şey olmamış gibi hepsini eski yerine koyarak uyumaya devam eder. İşin ilginci, ertesi akşam bir başkası kalkar yine gizlice cevizleri n’e bölüp artan bir tanesini maymuna verip kendi payını aldıktan sonra eski haline getirip yatar. Kalan kişilerde ilerleyen gecelerde benzer şekilde kalan hindistan cevizlerini n’e bölerek artan bir tanesini maymuna vermekte ve kendi paylarını almaktadır. Sonuçta bir sabah kalkarlar bu sefer hep beraber kalan cevizleri n’e bölerler herkes kendi payını alır ve maymuna da bir şey kalmaz. soru şudur:başlangıçta en az ne kadar hindistan cevizi vardı acaba?”
Yukarıdaki soru anlaşılsın diye sayısal örnek üzerinden açıklamaya çalışalım:
Örneğin 5 kişi olsunlar ve ortamda 15621 ceviz bulunsun.
Sorunun çözümünde her gün için kalkan kişinin kaç ceviz aldığı ve ne kadar ceviz arttığı aşağıdaki tabloda gösterilmiştir:
| Günlük alınan | Maymuna verilen | Kalan |
| 15621 | ||
| 3124 | 1 | 12496 |
| 2499 | 1 | 9996 |
| 1999 | 1 | 7996 |
| 1599 | 1 | 6396 |
| 1279 | 1 | 5116 |
Son gün kalan cevizler bölüşüldüğünde 5116 – 1 = 5115 / 5 = 1023 ceviz herkese pay edilmiş olur.
Yukarıdaki çözüm doğru olmakla birlikte sorudaki en az ihtimali taşımamaktadır.
Problemin çözümü için aşağıdaki özyineli denklem (recursive) yazılabilir.
N, ceviz sayısı n kişi sayısı ve m ise maymunun payı olmak üzere:
N=n a 1 + m
N – a 1 – m = n a 2 + m
N – a 1 – a 2 – 2m = n a 3 + m
…
N – a 1 – a 2 – a 3 – … – a n – nm = na + m
Yukarıdaki açık hali özyineli hale getirirsek :
N = n a 1 + m
(n-1) a 1 = n a 2 + m
(n-1) a 2 = n a 3 + m
…
(n-1) a n-1 = n a n + m
(n-1) a n = na + m
Yukarıdaki bu denklemi bir döngü içerisinde kodlayabiliriz. Örnek olarak verilen ceviz sayısı için kaç kişi olacağını bulan kodu aşağıdaki şekilde yazalım:
Yukarıdaki kodun çıktısı aşağıdaki şekildedir:
diğer sitelere oranla daha iyi bilgiler thanks 😀