15 Lineer Kongrüans Denklemleri
Diofant denklemlerinde “\(ax + by = c\) denkleminin tam sayı çözümleri” sorusunu yanıtlamıştık. Kongrüans dilinde aynı soru çok daha derli toplu bir biçim alır. Bu bölümde bu biçimi kuracak, çözüm sayısını tam olarak belirleyecek ve modüler aritmetikte “bölme” işleminin karşılığı olan çarpımsal tersi tanımlayacağız.
15.1 Tanım
Tanım 15.1 (Lineer Kongrüans Denklemi) \(a, b, n \in \mathbb{Z}\), \(1 < n\) ve \(x\) bir bilinmeyen olmak üzere
\[ax \equiv b \pmod n\]
ifadesine bir bilinmeyenli lineer (doğrusal) kongrüans denklemi denir.
\(x_0 \in \mathbb{Z}\) olmak üzere \(a x_0 \equiv b \pmod n\) ise, \(x_0\) tam sayısına bu denklemin bir çözümü denir. En az bir çözümü olan denkleme çözülebilir, hiç çözümü olmayana çözülebilir olmayan denir.
Örnek 15.1 (İki Örnek) \[4x \equiv 2 \pmod 6\]
denklemi çözülebilirdir; \(x_0 = 2\) bir çözümdür, çünkü \(4 \cdot 2 = 8 \equiv 2 \pmod 6\)’dır.
Buna karşılık
\[2x \equiv 1 \pmod 4\]
denkleminin hiç çözümü yoktur: \(2x\) daima çifttir, dolayısıyla \(2x - 1\) tektir ve \(4\) ile bölünemez.
Sonuç 12.2 gereği bir çözümün bütün kongrüleri de çözümdür. Bu yüzden çözümleri tek tek saymak anlamsızdır; sonsuz çok olurlar.
Anlaşma şudur: birbirine modülo \(n\) kongrü olmayan çözümler ayrı sayılır, kongrü olanlar aynı sayılır. “Çözüm sayısı” dediğimizde bunu kastedeceğiz.
15.2 Diofant Denklemleriyle Köprü
Lemma 15.1 (Kongrüans ile Diofant Denklemi Denktir) \(a, b, n \in \mathbb{Z}\) ve \(1 < n\) olsun.
\[ax \equiv b \pmod n\]
lineer kongrüans denklemini çözmek,
\[ax - ny = b\]
Diofant denklemini çözmeye eşdeğerdir.
İspat
\(x_0\) tam sayısı kongrüansın bir çözümü olsun. Tanım gereği \(n \mid a x_0 - b\)’dir; yani
\[a x_0 - b = n y_0\]
olacak biçimde bir \(y_0\) tam sayısı vardır. Düzenlersek
\[a x_0 - n y_0 = b\]
elde edilir; yani \((x_0, y_0)\) ikilisi Diofant denkleminin bir çözümüdür.
Tersine, \((x_0, y_0)\) Diofant denkleminin bir çözümü olsun: \(a x_0 - n y_0 = b\)’dir. Buradan
\[a x_0 - b = n y_0 \implies n \mid a x_0 - b \implies a x_0 \equiv b \pmod n\]
bulunur; yani \(x_0\) kongrüansın bir çözümüdür.
\(\blacksquare\)
15.3 Çözülebilirlik ve Çözüm Sayısı
Teorem 15.1 (Lineer Kongrüansın Çözümleri) \(a, b, n \in \mathbb{Z}\), \(1 < n\) ve \(d = \gcd(a, n)\) olsun.
1. \(ax \equiv b \pmod n\) denkleminin çözülebilir olması için gerek ve yeter koşul \(d \mid b\) olmasıdır.
2. \(d \mid b\) ise, denklemin modülo \(n\) birbirine kongrü olmayan tam \(d\) tane çözümü vardır.
İspat
1. Lemma 15.1 gereği kongrüansı çözmek \(ax - ny = b\) Diofant denklemini çözmeye denktir. Önerme 4.2 (3) gereği \(\gcd(a, -n) = \gcd(a,n) = d\)’dir. Teorem 8.1 (1) gereği bu denklem çözülebilirdir ancak ve ancak \(d \mid b\) ise.
2. \(d \mid b\) olsun ve \(x_0\) bir çözüm olsun. Teorem 8.1 (2) gereği Diofant denkleminin bütün çözümlerinde
\[x = x_0 + \frac{n}{d}\,t, \qquad t \in \mathbb{Z}\]
olur. (Burada \(-n\) katsayısının işareti \(t\)’nin işaretine yansır; \(t\) bütün tam sayıları dolaştığından bir fark yaratmaz.)
Şimdi bu çözümlerden hangilerinin modülo \(n\) aynı sayıldığını belirleyelim. \(t_1\) ile \(t_2\) için elde edilen çözümler için
\[ \begin{aligned} x_0 + \frac{n}{d}t_1 \equiv x_0 + \frac{n}{d}t_2 \pmod n &\iff n \ \Big| \ \frac{n}{d}\left( t_1 - t_2 \right) \\ &\iff \frac{n}{d}\left( t_1 - t_2 \right) = n s \quad (s \in \mathbb{Z}) \\ &\iff t_1 - t_2 = d s \\ &\iff t_1 \equiv t_2 \pmod d \end{aligned} \]
Demek ki iki çözüm modülo \(n\) kongrüdür ancak ve ancak karşılık gelen \(t\) değerleri modülo \(d\) kongrü ise.
\(t\) parametresi modülo \(d\) tam \(d\) farklı sınıf ürettiğinden — örneğin \(t = 0, 1, \dots, d-1\) değerleri bir tam kalan sistemidir — birbirine kongrü olmayan çözüm sayısı tam olarak \(d\)’dir:
\[x \equiv x_0,\ x_0 + \frac{n}{d},\ x_0 + \frac{2n}{d},\ \dots,\ x_0 + \frac{(d-1)n}{d} \pmod n\]
\(\blacksquare\)
Sonuç 15.1 (Aralarında Asal Hâlde Tek Çözüm) \(a, b, n \in \mathbb{Z}\), \(1 < n\) ve \(\gcd(a, n) = 1\) olsun. Bu durumda
\[ax \equiv b \pmod n\]
denkleminin modülo \(n\) tek çözümü vardır. \(x_0\) bu çözümse, bütün tam sayı çözümlerinin kümesi
\[\{ x_0 + nk \ : \ k \in \mathbb{Z} \}\]
biçimindedir.
Bu, Teorem 15.1’ın \(d = 1\) hâlidir: \(1 \mid b\) daima doğrudur, dolayısıyla denklem her zaman çözülebilirdir ve tam \(1\) çözümü vardır.
15.4 Çözüm Teknikleri
Pratikte iki yol kullanılır. Birincisi Diofant denklemine geçip Öklid algoritmasıyla ilerlemek, ikincisi ise doğrudan kongrüans üzerinde çalışıp katsayıyı \(\pm 1\)’e indirmektir. İkinci yol genellikle daha kısadır.
\(ax \equiv b \pmod n\) denklemini çözerken, her iki tarafı modülle aralarında asal bir sayıyla çarpmak serbesttir (\(\thinspace\)Teorem 12.1 (e)\(\thinspace\)) ve bu işlem tersine çevrilebilir olduğundan çözüm kümesini değiştirmez.
Amaç, \(a\) katsayısını \(1\) veya \(-1\)’e indirecek bir çarpan bulmaktır. \(a\)’nın modüle yakın bir katını üretecek çarpanlar aranır.
Örnek 15.2 (\(35x \equiv 21 \pmod{42}\)) \(35x \equiv 21 \pmod{42}\) denklemini çözünüz.
Çözüm
Çözülebilirlik. \(\gcd(35, 42) = 7\) ve \(7 \mid 21\) olduğundan denklem çözülebilirdir; Teorem 15.1 gereği modülo \(42\)’de \(7\) tane çözümü vardır.
Sadeleştirme. \(7\) sayısı \(35\)’i, \(21\)’i ve \(42\)’yi böldüğünden denklemin tamamını \(7\)’ye bölebiliriz — modülün de bölündüğüne dikkat ediniz:
\[5x \equiv 3 \pmod 6\]
(Bu adımın geçerliliği Teorem 12.3’den gelir.)
Katsayıyı indirme. \(\gcd(5,6) = 1\)’dir. Sağ tarafa \(6\)’nın katlarını ekleyerek \(5\)’in katını yakalayalım:
\[3 \equiv 3 + 12 = 15 \pmod 6\]
Buradan
\[5x \equiv 15 \pmod 6\]
\(\gcd(5,6) = 1\) olduğundan Sonuç 12.1 (1) gereği \(5\) sadeleştirilebilir:
\[x \equiv 3 \pmod 6\]
Çözüm kümesi. Bütün tam sayı çözümleri:
\[\{ 3 + 6t \ : \ t \in \mathbb{Z} \}\]
Modülo \(42\)’ye göre birbirine kongrü olmayan \(7\) çözüm ise şunlardır:
\[x \equiv 3,\ 9,\ 15,\ 21,\ 27,\ 33,\ 39 \pmod{42}\]
(Sağlama: \(35 \cdot 9 = 315 = 7 \cdot 42 + 21\) ✓)
\(\blacksquare\)
Örnek 15.3 (\(140x \equiv 133 \pmod{301}\)) \(140x \equiv 133 \pmod{301}\) denklemini çözünüz.
Çözüm
Çözülebilirlik. Öklid algoritmasıyla:
\[ \begin{aligned} 301 &= 2 \cdot 140 + 21 \\ 140 &= 6 \cdot 21 + 14 \\ 21 &= 1 \cdot 14 + 7 \\ 14 &= 2 \cdot 7 + 0 \end{aligned} \]
O hâlde \(d = \gcd(140, 301) = 7\)’dir. \(133 = 19 \cdot 7\) olduğundan \(7 \mid 133\)’tür; denklem çözülebilirdir ve modülo \(301\)’de \(7\) çözümü vardır.
Sadeleştirme. Denklemi \(7\)’ye bölelim (modül dâhil):
\[20x \equiv 19 \pmod{43}\]
Katsayıyı indirme. \(\gcd(20, 43) = 1\)’dir. Her iki tarafı \(2\) ile çarpalım:
\[40x \equiv 38 \pmod{43}\]
\(40 = 43 - 3\) olduğundan \(40 \equiv -3\)’tür:
\[-3x \equiv 38 \pmod{43}\]
Her iki tarafı \(-1\) ile çarpalım ve \(-38 \equiv 5 \pmod{43}\) olduğunu kullanalım:
\[3x \equiv 5 \pmod{43}\]
Şimdi \(3\)’ü yok etmek için \(14\) ile çarpalım (\(3 \cdot 14 = 42 \equiv -1\)):
\[42x \equiv 70 \pmod{43} \implies -x \equiv 27 \pmod{43}\]
(çünkü \(70 = 43 + 27\)). Her iki tarafı \(-1\) ile çarparsak
\[x \equiv -27 \equiv 16 \pmod{43}\]
(Sağlama: \(20 \cdot 16 = 320 = 7 \cdot 43 + 19\) ✓)
Çözüm kümesi. Bütün tam sayı çözümleri \(\{16 + 43t : t \in \mathbb{Z}\}\)’dir. Modülo \(301\)’de birbirine kongrü olmayan \(7\) çözüm:
\[x \equiv 16,\ 59,\ 102,\ 145,\ 188,\ 231,\ 274 \pmod{301}\]
\(\blacksquare\)
Örnek 15.4 (İki Kısa Örnek) Aşağıdaki denklemleri çözünüz.
a) \(25x \equiv 15 \pmod{29}\) b) \(36x \equiv 8 \pmod{102}\)
Çözüm
a) \(29\) asal ve \(29 \nmid 25\) olduğundan \(\gcd(25, 29) = 1\)’dir; Sonuç 15.1 gereği tek çözüm vardır.
\(25 = 29 - 4\) olduğundan \(25 \equiv -4 \pmod{29}\)’dur:
\[-4x \equiv 15 \pmod{29}\]
Her iki tarafı \(7\) ile çarpalım (\(-4 \cdot 7 = -28 \equiv 1 \pmod{29}\)):
\[-28x \equiv 105 \pmod{29} \implies x \equiv 105 \pmod{29}\]
\(105 = 3 \cdot 29 + 18\) olduğundan
\[x \equiv 18 \pmod{29}\]
(Sağlama: \(25 \cdot 18 = 450 = 15 \cdot 29 + 15\) ✓)
b) \(\gcd(36, 102)\) değerini bulalım:
\[102 = 2 \cdot 36 + 30, \qquad 36 = 1 \cdot 30 + 6, \qquad 30 = 5 \cdot 6 + 0\]
O hâlde \(d = 6\)’dır. Ancak \(6 \nmid 8\)’dir; Teorem 15.1 (1) gereği denklemin hiç çözümü yoktur.
\(\blacksquare\)
15.5 Çarpımsal Ters
Reel sayılarda \(ax = b\) denklemini \(x = a^{-1}b\) diye çözeriz. Modüler aritmetikte de benzer bir “ters” kavramı vardır — ama her sayının tersi yoktur.
Tanım 15.2 (Çarpımsal Ters) \(a, b, n \in \mathbb{Z}\) ve \(1 < n\) olsun. Eğer
\[ab \equiv 1 \pmod n\]
ise \(b\) tam sayısına \(a\)’nın modülo \(n\) çarpımsal tersi denir.
Önerme 15.1 (Tersin Varlığı ve Tekliği) \(a, n \in \mathbb{Z}\) ve \(1 < n\) olsun.
1. \(a\) sayısının modülo \(n\) çarpımsal tersinin var olması için gerek ve yeter koşul \(\gcd(a, n) = 1\) olmasıdır.
2. Ters varsa modülo \(n\)’ye göre tek türlü belirlidir.
Gerçekten de \(a\)’nın tersinin var olması, \(ax \equiv 1 \pmod n\) denkleminin çözülebilir olması demektir. Teorem 15.1 (1) gereği bu, \(\gcd(a,n) \mid 1\), yani \(\gcd(a,n) = 1\) koşuluna denktir. Bu durumda Sonuç 15.1 gereği çözüm modülo \(n\) tektir.
\(\gcd(a,n) = 1\) olduğunda \(ax \equiv b \pmod n\) denklemi tek adımda çözülür: her iki tarafı \(a\)’nın tersi olan \(a^{-1}\) ile çarpmak yeterlidir:
\[x \equiv a^{-1} b \pmod n\]
Yani modüler aritmetikte “bölme”, tersle çarpmaktır ve yalnızca modülle aralarında asal sayılar için tanımlıdır.
Örnek 15.5 (\(49\) Sayısının Modülo \(120\) Tersi) \(49\) tam sayısının modülo \(120\) çarpımsal tersini bulunuz.
Çözüm
Önce tersin var olduğunu doğrulayalım; Öklid algoritmasını uygulayalım:
\[ \begin{aligned} 120 &= 2 \cdot 49 + 22 \\ 49 &= 2 \cdot 22 + 5 \\ 22 &= 4 \cdot 5 + 2 \\ 5 &= 2 \cdot 2 + 1 \\ 2 &= 2 \cdot 1 + 0 \end{aligned} \]
\(\gcd(49, 120) = 1\) olduğundan Önerme 15.1 gereği ters vardır ve tektir.
Şimdi geriye doğru yerine koyalım:
\[ \begin{aligned} 1 &= 5 - 2 \cdot 2 \\ &= 5 - 2\left( 22 - 4 \cdot 5 \right) \\ &= 9 \cdot 5 - 2 \cdot 22 \\ &= 9\left( 49 - 2 \cdot 22 \right) - 2 \cdot 22 \\ &= 9 \cdot 49 - 20 \cdot 22 \\ &= 9 \cdot 49 - 20\left( 120 - 2 \cdot 49 \right) \\ &= 49 \cdot 49 - 120 \cdot 20 \end{aligned} \]
(Sağlama: \(2401 - 2400 = 1\) ✓)
Bu eşitliği modülo \(120\) okuyalım:
\[49 \cdot 49 \equiv 1 \pmod{120}\]
O hâlde \(49\) sayısının modülo \(120\) tersi yine \(49\)’dur.
\(\blacksquare\)
\(49^2 = 2401 = 20 \cdot 120 + 1\) olması bir rastlantı değildir: \(49^2 - 1 = 48 \cdot 50 = 2400\) ve \(120 \mid 2400\)’dür. Kendi tersi olan sayılar, \(x^2 \equiv 1 \pmod n\) denkleminin çözümleridir; bu denklemin kaç çözümü olduğu Wilson teoremi bölümünde tekrar karşımıza çıkacak.
15.6 Diofant Denklemlerini Kongrüansla Çözmek
Lemma 15.1 iki yönlüdür: kongrüansları Diofant denklemine çevirebildiğimiz gibi, Diofant denklemlerini de kongrüansa çevirip çözebiliriz. Katsayılardan biri küçükse bu ikinci yol çok daha hızlıdır.
Örnek 15.6 (\(5x - 53y = 17\)) \(5x - 53y = 17\) Diofant denklemini kongrüans kullanarak çözünüz.
Çözüm
Denklemi modülo \(53\) okuyalım; \(53y\) terimi kaybolur:
\[5x \equiv 17 \pmod{53}\]
\(\gcd(5, 53) = 1\) olduğundan tek çözüm vardır. Katsayıyı indirmek için her iki tarafı \(21\) ile çarpalım (\(5 \cdot 21 = 105 = 2 \cdot 53 - 1 \equiv -1\)):
\[105x \equiv 357 \pmod{53} \implies -x \equiv 357 \pmod{53}\]
\(357 = 6 \cdot 53 + 39\) olduğundan \(357 \equiv 39\)’dur:
\[-x \equiv 39 \implies x \equiv -39 \equiv 14 \pmod{53}\]
(Sağlama: \(5 \cdot 14 = 70 = 53 + 17\) ✓)
\(x_0 = 14\) için karşılık gelen \(y\) değerini bulalım:
\[5 \cdot 14 - 53 y_0 = 17 \implies 53 y_0 = 70 - 17 = 53 \implies y_0 = 1\]
Teorem 8.1 (2) gereği genel çözüm (burada \(d = \gcd(5, -53) = 1\)):
\[x = 14 + 53t, \qquad y = 1 + 5t \qquad (t \in \mathbb{Z})\]
(Sağlama: \(5(14 + 53t) - 53(1 + 5t) = 70 + 265t - 53 - 265t = 17\) ✓)
\(\blacksquare\)
Örnek 15.7 (\(12x + 25y = 331\)) \(12x + 25y = 331\) Diofant denklemini kongrüans kullanarak çözünüz.
Çözüm
Denklemi modülo \(25\) okuyalım:
\[12x \equiv 331 \pmod{25}\]
\(331 = 13 \cdot 25 + 6\) olduğundan sağ tarafı küçültelim:
\[12x \equiv 6 \pmod{25}\]
\(\gcd(12, 25) = 1\)’dir. Her iki tarafı \(2\) ile çarpalım (\(12 \cdot 2 = 24 \equiv -1\)):
\[24x \equiv 12 \pmod{25} \implies -x \equiv 12 \pmod{25} \implies x \equiv -12 \equiv 13 \pmod{25}\]
(Sağlama: \(12 \cdot 13 = 156 = 6 \cdot 25 + 6\) ✓)
\(x_0 = 13\) için \(y\) değerini bulalım:
\[12 \cdot 13 + 25 y_0 = 331 \implies 25 y_0 = 331 - 156 = 175 \implies y_0 = 7\]
Genel çözüm:
\[x = 13 + 25t, \qquad y = 7 - 12t \qquad (t \in \mathbb{Z})\]
Sağlama. Bu çift, her \(t\) için denklemi gerçekten sağlar ✓:
\[12(13 + 25t) + 25(7 - 12t) = 156 + 300t + 175 - 300t = 331\]
\(\blacksquare\)
15.7 Çalışma Problemleri
Alıştırma 15.1 (Lineer Kongrüansları Çözme) Aşağıdaki denklemleri çözünüz; çözümü olmayanları belirtiniz ve çözüm sayısını yazınız.
a) \(3x \equiv 5 \pmod 7\) b) \(6x \equiv 15 \pmod{21}\) c) \(9x \equiv 12 \pmod{21}\)
d) \(8x \equiv 6 \pmod{14}\) e) \(4x \equiv 3 \pmod{10}\) f) \(17x \equiv 3 \pmod{29}\)
Alıştırma 15.2 (Çarpımsal Tersler) Aşağıdaki tersleri bulunuz; yoksa nedenini açıklayınız.
a) \(7\)’nin modülo \(26\) tersi b) \(10\)’un modülo \(27\) tersi
c) \(6\)’nın modülo \(9\) tersi d) \(2\)’nin modülo \(31\) tersi
Alıştırma 15.3 (Asal Modülde Tersi Bulmanın Bir Yolu) \(p\) bir asal sayı, \(a, b \in \mathbb{Z}\) ve \(\gcd(p, a) = 1\) olsun.
a) İleride ispatlayacağımız Fermat teoremini kullanarak — bu teorem \(a^{p-1} \equiv 1 \pmod p\) der — \(a^{p-2}b\) tam sayısının
\[ax \equiv b \pmod p\]
denkleminin bir çözümü olduğunu gösteriniz.
b) Bu yöntemle \(2x \equiv 1 \pmod{31}\) ve \(6x \equiv 5 \pmod{11}\) denklemlerini çözünüz.
Alıştırma 15.4 (Kongrüansla Diofant Denklemleri) Aşağıdaki Diofant denklemlerini kongrüansa çevirerek çözünüz.
a) \(7x + 9y = 100\) b) \(11x - 13y = 5\) c) \(6x + 15y = 21\)