8 Diofant Denklemleri
Bir denklemin çözümlerini reel sayılar arasında değil, yalnızca tam sayılar arasında aramak bambaşka bir problemdir. \(172x + 20y = 1000\) denkleminin sonsuz çok reel çözümü olduğu açıktır — bir doğru denklemidir. Asıl soru şudur: bu doğru üzerinde her iki koordinatı da tam sayı olan noktalar var mıdır, varsa hangileridir?
Şaşırtıcı biçimde bu sorunun cevabı, önceki bölümlerde kurduğumuz araçlarda çoktan gizlidir.
8.1 Tanım
Tanım 8.1 (Birinci Dereceden İki Bilinmeyenli Diofant Denklemi) \(a\) ile \(b\) ikisi birden sıfır olmayan tam sayılar, \(c\) herhangi bir tam sayı ve \(x, y\) birer bilinmeyen olmak üzere
\[ax + by = c\]
denklemine bir (doğrusal) Diofant denklemi denir.
\(x_0, y_0\) birer tam sayı olmak üzere \(a x_0 + b y_0 = c\) ise, \((x_0, y_0)\) ikilisine bu denklemin bir çözümü denir. En az bir çözümü olan denkleme çözülebilir, hiç çözümü olmayana çözülemez denir.
\(ax + by\) ifadesi, \(a\) ile \(b\)’nin bir doğrusal birleşimidir. Sonuç 4.2’de bütün doğrusal birleşimlerin kümesini belirlemiştik:
\[\{ ax + by : x, y \in \mathbb{Z} \} = \{ dk : k \in \mathbb{Z} \}, \qquad d = \gcd(a,b)\]
Yani \(ax + by\) ifadesi tam olarak \(\gcd(a,b)\)’nin katlarını üretebilir, başka hiçbir değeri üretemez. Diofant denkleminin çözülebilirlik ölçütü bu gözlemin doğrudan okunuşudur.
8.2 Çözülebilirlik ve Genel Çözüm
Teorem 8.1 (Diofant Denkleminin Çözümü) \(a\) ile \(b\) ikisi birden sıfır olmayan tam sayılar, \(c \in \mathbb{Z}\) ve \(d = \gcd(a,b)\) olsun.
1. \(ax + by = c\) denkleminin çözülebilir olması için gerek ve yeter koşul \(d \mid c\) olmasıdır.
2. \((x_0, y_0)\) bu denklemin bir çözümü ise, denklemin bütün çözümleri \(t\) tam sayılarını dolaşmak üzere
\[x = x_0 + \frac{b}{d}\,t, \qquad y = y_0 - \frac{a}{d}\,t\]
biçimindedir.
İspat
Genelliği bozmadan \(b \neq 0\) olduğunu varsayabiliriz (aksi hâlde \(a \neq 0\) olur ve \(x\) ile \(y\)’nin rolleri değiştirilir).
\(d = \gcd(a,b)\) olduğundan \(d \mid a\) ve \(d \mid b\)’dir; yazalım:
\[a = dk, \qquad b = ds\]
Sonuç 5.1 gereği \(\gcd(k, s) = 1\)’dir. Ayrıca \(b \neq 0\) olduğundan \(s \neq 0\)’dır. Son olarak Bézout teoremi gereği
\[d = au + bv\]
olacak biçimde \(u, v\) tam sayıları vardır.
1. Çözülebilirlik ölçütü.
(\(\Rightarrow\)) Denklem çözülebilir olsun; \(a x_0 + b y_0 = c\) olacak biçimde \(x_0, y_0\) tam sayıları vardır. \(d \mid a\) ve \(d \mid b\) olduğundan Teorem 3.1 (6) gereği
\[d \mid a x_0 + b y_0 = c\]
(\(\Leftarrow\)) \(d \mid c\) olsun; \(c = dz\) olacak biçimde bir \(z\) tam sayısı vardır. Bézout ifadesini kullanalım:
\[c = dz = (au + bv)z = a(uz) + b(vz)\]
Demek ki \((uz,\ vz)\) ikilisi denklemin bir çözümüdür.
2. Bütün çözümler. \((x_0, y_0)\) bir çözüm olsun. Denklemin çözüm kümesine \(S\), teoremde tarif edilen kümeye \(T\) diyelim:
\[T = \left\{ \left( x_0 + \frac{b}{d}t,\ \ y_0 - \frac{a}{d}t \right) \ : \ t \in \mathbb{Z} \right\}\]
\(T \subseteq S\). \(t \in \mathbb{Z}\) olsun ve tarif edilen ikiliyi denklemde yerine koyalım:
\[ \begin{aligned} a\left( x_0 + \frac{b}{d}t \right) + b\left( y_0 - \frac{a}{d}t \right) &= a x_0 + \frac{ab}{d}t + b y_0 - \frac{ab}{d}t \\ &= a x_0 + b y_0 \\ &= c \end{aligned} \]
Görüldüğü gibi \(t\) içeren terimler birbirini götürür; her \(t\) için bir çözüm elde edilir.
\(S \subseteq T\). \((x_1, y_1)\) herhangi bir çözüm olsun. O hâlde
\[a x_1 + b y_1 = c = a x_0 + b y_0\]
Terimleri düzenleyelim:
\[a(x_1 - x_0) = b(y_0 - y_1)\]
\(a = dk\) ve \(b = ds\) yazıp \(d \neq 0\) olduğundan sadeleştirelim:
\[dk(x_1 - x_0) = ds(y_0 - y_1) \implies k(x_1 - x_0) = s(y_0 - y_1)\]
Bu eşitlik \(s \mid k(x_1 - x_0)\) olduğunu söyler. \(\gcd(s, k) = 1\) olduğundan Teorem 5.1 gereği
\[s \mid x_1 - x_0\]
bulunur; yani \(x_1 - x_0 = st\) olacak biçimde bir \(t \in \mathbb{Z}\) vardır. Buradan
\[x_1 = x_0 + st = x_0 + \frac{b}{d}\,t\]
elde edilir. Şimdi bunu yukarıdaki eşitlikte yerine koyalım:
\[k \cdot st = s(y_0 - y_1)\]
\(s \neq 0\) olduğundan sadeleştirebiliriz:
\[kt = y_0 - y_1 \implies y_1 = y_0 - kt = y_0 - \frac{a}{d}\,t\]
Demek ki \((x_1, y_1) \in T\)’dir.
İki kapsama birlikte \(S = T\) verir.
\(\blacksquare\)
Teoremin ikinci kısmı, problemin bütün zorluğunu tek bir çözüm bulmaya indirger. O tek çözümü bulduktan sonra sonsuz çoklukta olan diğerleri hiçbir ek çaba gerektirmez; yalnızca \(b/d\) ve \(a/d\) katsayılarını yazmak yeterlidir.
Adımların sırası şudur:
- \(d = \gcd(a,b)\) hesaplanır ve \(d \mid c\) olup olmadığına bakılır.
- Öklid algoritmasıyla \(d = a u + b v\) yazılır.
- Her iki taraf \(c/d\) ile çarpılarak özel çözüm elde edilir.
- Genel çözüm formülü yazılır.
8.3 Çözümlü Örnekler
Örnek 8.1 (Çözümü Olmayan Bir Denklem) \(24x + 30y = 5\) Diofant denkleminin çözümü var mıdır?
Çözüm
Çözülebilirlik ölçütünü uygulayalım:
\[\gcd(24, 30) = 6\]
Oysa \(6 \nmid 5\)’tir. Teorem 8.1 (1) gereği denklemin hiçbir tam sayı çözümü yoktur.
Sezgisel açıklama: sol taraftaki her iki terim de \(6\)’nın katı olduğundan toplam daima \(6\)’nın katı olmak zorundadır; \(5\) ise değildir.
\(\blacksquare\)
Örnek 8.2 (\(132x + 84y = 24\)) \(132x + 84y = 24\) Diofant denkleminin tüm tam sayı çözümlerini bulunuz.
Çözüm
1. Çözülebilirlik. Öklid algoritmasıyla en büyük ortak böleni bulalım:
\[ \begin{aligned} 132 &= 1 \cdot 84 + 48 \\ 84 &= 1 \cdot 48 + 36 \\ 48 &= 1 \cdot 36 + 12 \\ 36 &= 3 \cdot 12 + 0 \end{aligned} \]
O hâlde \(d = \gcd(132, 84) = 12\)’dir. \(24 = 2 \cdot 12\) olduğundan \(12 \mid 24\)’tür; denklem çözülebilirdir.
2. Bézout katsayıları. Geriye doğru yerine koyalım:
\[ \begin{aligned} 12 &= 48 - 36 \\ &= 48 - \left( 84 - 48 \right) \\ &= 2 \cdot 48 - 84 \\ &= 2\left( 132 - 84 \right) - 84 \\ &= 132 \cdot 2 + 84 \cdot (-3) \end{aligned} \]
(Sağlama: \(264 - 252 = 12\) ✓)
3. Özel çözüm. Sağ taraf \(12\) değil \(24\) olduğundan eşitliğin iki tarafını \(2\) ile çarpalım:
\[24 = 132 \cdot 4 + 84 \cdot (-6)\]
(Sağlama: \(528 - 504 = 24\) ✓) Yani \(x_0 = 4\), \(y_0 = -6\)’dır.
4. Genel çözüm. Teorem 8.1 (2) gereği
\[x = 4 + \frac{84}{12}\,t = 4 + 7t, \qquad y = -6 - \frac{132}{12}\,t = -6 - 11t \qquad (t \in \mathbb{Z})\]
Sağlama. Bu çift, her \(t\) için denklemi gerçekten sağlar ✓:
\[132(4+7t) + 84(-6-11t) = 528 + 924t - 504 - 924t = 24\]
\(\blacksquare\)
Örnek 8.3 (\(182x + 70y = 210\)) \(182x + 70y = 210\) Diofant denklemini çözünüz.
Çözüm
1. Çözülebilirlik. Örnek 6.1’de \(\gcd(182, 70) = 14\) bulmuştuk. \(210 = 15 \cdot 14\) olduğundan \(14 \mid 210\)’dur; denklem çözülebilirdir.
2. Bézout katsayıları. Yine aynı örnekte
\[14 = 182 \cdot 2 + 70 \cdot (-5)\]
elde etmiştik.
3. Özel çözüm. Her iki tarafı \(15\) ile çarpalım:
\[210 = 182 \cdot 30 + 70 \cdot (-75)\]
(Sağlama: \(5460 - 5250 = 210\) ✓) Yani \(x_0 = 30\), \(y_0 = -75\)’tir.
4. Genel çözüm.
\[x = 30 + \frac{70}{14}\,t = 30 + 5t, \qquad y = -75 - \frac{182}{14}\,t = -75 - 13t \qquad (t \in \mathbb{Z})\]
Çözüm kümesi:
\[\big\{ (30 + 5t,\ -75 - 13t) \ : \ t \in \mathbb{Z} \big\}\]
\(\blacksquare\)
8.4 Çözümleri Bir Aralıkla Sınırlamak
Uygulamalarda genellikle bütün çözümler değil, belli bir aralığa düşenler istenir. Genel çözüm parametreli biçimde yazıldığından bu, \(t\) üzerinde basit bir eşitsizliğe dönüşür.
Örnek 8.4 (Belli Bir Aralıktaki Çözümler) \(172x + 20y = 1000\) Diofant denkleminin \(495 < x < 510\) koşuluna uyan tüm çözümlerini bulunuz.
Çözüm
1. Çözülebilirlik. Öklid algoritması:
\[ \begin{aligned} 172 &= 8 \cdot 20 + 12 \\ 20 &= 1 \cdot 12 + 8 \\ 12 &= 1 \cdot 8 + 4 \\ 8 &= 2 \cdot 4 + 0 \end{aligned} \]
O hâlde \(d = \gcd(172, 20) = 4\)’tür. \(1000 = 250 \cdot 4\) olduğundan \(4 \mid 1000\)’dir; denklem çözülebilirdir.
2. Bézout katsayıları.
\[ \begin{aligned} 4 &= 12 - 8 \\ &= 12 - \left( 20 - 12 \right) \\ &= 2 \cdot 12 - 20 \\ &= 2\left( 172 - 8 \cdot 20 \right) - 20 \\ &= 172 \cdot 2 + 20 \cdot (-17) \end{aligned} \]
(Sağlama: \(344 - 340 = 4\) ✓)
3. Özel çözüm. Her iki tarafı \(250\) ile çarpalım:
\[1000 = 172 \cdot 500 + 20 \cdot (-4250)\]
Yani \(x_0 = 500\), \(y_0 = -4250\)’dir.
4. Genel çözüm.
\[x = 500 + \frac{20}{4}\,t = 500 + 5t, \qquad y = -4250 - \frac{172}{4}\,t = -4250 - 43t\]
5. Aralık koşulu. Şimdi \(495 < x < 510\) eşitsizliğini \(t\) cinsinden çözelim:
\[ \begin{aligned} 495 &< 500 + 5t < 510 \\ -5 &< 5t < 10 \\ -1 &< t < 2 \end{aligned} \]
Bu aralıktaki tam sayılar \(t = 0\) ve \(t = 1\)’dir.
- \(t = 0\) için: \((x, y) = (500,\ -4250)\)
- \(t = 1\) için: \((x, y) = (505,\ -4293)\)
(Sağlama: \(172 \cdot 505 + 20 \cdot (-4293) = 86860 - 85860 = 1000\) ✓)
\(\blacksquare\)
Diofant denklemleri, lineer kongrüanslarla birebir aynı problemdir; nitekim
\[ax + by = c \iff ax \equiv c \pmod{b}\]
denkliği vardır. Kongrüanslar bölümünde bu köprüyü kuracak ve aynı denklemleri bu kez kongrüans diliyle çözeceğiz.
Daha fazla çözümlü örnek için Sayılar Teorisi II’deki Doğrusal Diofant Denklemleri bölümüne de bakabilirsiniz.
8.5 Çalışma Problemleri
Alıştırma 8.1 (Diofant Denklemleri) Aşağıdaki denklemlerin bütün tam sayı çözümlerini bulunuz; çözümü olmayanları belirtiniz.
a) \(56x + 72y = 40\) b) \(24x + 138y = 18\) c) \(221x + 35y = 11\) d) \(84x + 990y = 186\)
e) \(18x + 14y = 48\) f) \(60x + 18y = 97\)
Alıştırma 8.2 (Pozitif Çözümler) \(5x + 3y = 52\) denkleminin pozitif tam sayı çözümlerini bulunuz.
İpucu: Önce genel çözümü yazınız, ardından \(x > 0\) ve \(y > 0\) eşitsizliklerini \(t\) cinsinden çözüp iki koşulu birlikte sağlayan \(t\) değerlerini belirleyiniz.
Alıştırma 8.3 (Bir Uygulama) Bir kırtasiye, tanesi \(7\) liradan defter ve tanesi \(11\) liradan kalem satmaktadır. Toplam \(100\) lira harcayan bir müşteri kaç defter ve kaç kalem almış olabilir?
İpucu: \(7x + 11y = 100\) denkleminin negatif olmayan çözümlerini arayınız.