16 Çin Kalan Teoremi
“Bir sayı \(9\) ile bölündüğünde \(7\), \(10\) ile bölündüğünde \(4\), \(13\) ile bölündüğünde \(12\) kalanını veriyor. Bu sayı kaçtır?” Bu tür sorular, birden çok kongrüansın aynı anda sağlanmasını ister. Çin kalan teoremi, modüller uygun koşulu sağladığında böyle bir sayının daima var olduğunu ve — büyük bir modüle göre — tek türlü belirli olduğunu söyler.
16.1 Teorem
Teorem 16.1 (Çin Kalan Teoremi) \(1 < n_1, n_2, \dots, n_r \in \mathbb{Z}\) ikişer ikişer aralarında asal olsun; yani her \(i \neq j\) için \(\gcd(n_i, n_j) = 1\) olsun. Bu durumda
\[ \begin{aligned} x &\equiv a_1 \pmod{n_1} \\ x &\equiv a_2 \pmod{n_2} \\ &\ \ \vdots \\ x &\equiv a_r \pmod{n_r} \end{aligned} \]
denklem sisteminin bir çözümü vardır ve bu çözüm
\[n = n_1 n_2 \cdots n_r\]
modülüne göre tek türlü belirlidir. \(x_0\) bir çözümse, bütün çözümlerin kümesi
\[\{ x_0 + nk \ : \ k \in \mathbb{Z} \}\]
biçimindedir.
İspat
1. Varlık. Her \(i\) için
\[N_i := \frac{n}{n_i} = n_1 \cdots n_{i-1} \, n_{i+1} \cdots n_r\]
tanımlayalım; yani \(N_i\), çarpımdan \(n_i\) çıkarılarak elde edilir.
\(\gcd(N_i, n_i) = 1\)’dir. Gerçekten de \(N_i\) çarpımındaki her \(n_j\) (\(j \neq i\)) hipotez gereği \(n_i\) ile aralarında asaldır; Teorem 5.3’in tekrarlı uygulanmasıyla çarpımları da \(n_i\) ile aralarında asaldır.
Bu yüzden Sonuç 15.1 gereği her \(i\) için
\[N_i x \equiv 1 \pmod{n_i}\]
denkleminin bir \(x_i\) çözümü vardır. Şimdi aday çözümümüzü kuralım:
\[x_0 := a_1 N_1 x_1 + a_2 N_2 x_2 + \cdots + a_r N_r x_r\]
Bu sayı bütün denklemleri sağlar. Bir \(i\) sabitleyelim ve \(x_0\)’ı modülo \(n_i\) inceleyelim. \(j \neq i\) olduğunda \(n_i\) sayısı \(N_j\) çarpımının bir çarpanıdır; dolayısıyla
\[N_j \equiv 0 \pmod{n_i} \qquad (j \neq i)\]
O hâlde toplamda \(i\) dışındaki bütün terimler kaybolur:
\[x_0 \equiv a_i N_i x_i \pmod{n_i}\]
\(x_i\) sayısı \(N_i x \equiv 1 \pmod{n_i}\) denkleminin çözümü olduğundan \(N_i x_i \equiv 1\)’dir; buradan
\[x_0 \equiv a_i \cdot 1 = a_i \pmod{n_i}\]
bulunur. Bu her \(i\) için geçerli olduğundan \(x_0\) sistemin bir çözümüdür.
2. Teklik. \(x_0\) ile \(x_1\) sistemin iki çözümü olsun. Her \(i\) için
\[x_0 \equiv a_i \equiv x_1 \pmod{n_i} \implies n_i \mid x_0 - x_1\]
Demek ki \(x_0 - x_1\) sayısı \(n_1, \dots, n_r\) sayılarının ortak katıdır. Bu sayılar ikişer ikişer aralarında asal olduğundan Teorem 5.2’ın tekrarlı uygulanmasıyla çarpımları da böler:
\[n = n_1 n_2 \cdots n_r \ \mid \ x_0 - x_1\]
Yani \(x_0 \equiv x_1 \pmod n\)’dir; çözüm modülo \(n\) tektir.
Son olarak \(x_0\) bir çözümse, \(x_0 + nk\) sayıları da her \(n_i\) modülünde \(x_0\)’a kongrüdür (çünkü \(n_i \mid n\)); dolayısıyla hepsi çözümdür.
\(\blacksquare\)
İspat yalnızca varlığı göstermez, çözümü kurar. Adımlar şunlardır:
- \(n = n_1 n_2 \cdots n_r\) hesaplanır.
- Her \(i\) için \(N_i = n / n_i\) bulunur.
- Her \(i\) için \(N_i x \equiv 1 \pmod{n_i}\) denklemi çözülüp bir \(x_i\) bulunur.
- \(x_0 = \sum_i a_i N_i x_i\) hesaplanır ve modülo \(n\) indirgenir.
16.2 Çözümlü Örnekler
Örnek 16.1 (Üç Denklemli Bir Sistem) \[x \equiv 1 \pmod 3, \qquad x \equiv 17 \pmod 5, \qquad x \equiv -15 \pmod 7\]
sistemini çözünüz.
Çözüm
Hazırlık. Önce sağ tarafları küçültelim:
\[17 \equiv 2 \pmod 5, \qquad -15 \equiv -15 + 21 = 6 \pmod 7\]
Sistem şu hâle gelir:
\[x \equiv 1 \pmod 3, \qquad x \equiv 2 \pmod 5, \qquad x \equiv 6 \pmod 7\]
\(3, 5, 7\) ikişer ikişer aralarında asaldır (üçü de farklı asal); teorem uygulanabilir.
1. Adım. \(n = 3 \cdot 5 \cdot 7 = 105\).
2. Adım.
\[N_1 = \frac{105}{3} = 35, \qquad N_2 = \frac{105}{5} = 21, \qquad N_3 = \frac{105}{7} = 15\]
3. Adım. Her biri için \(N_i x \equiv 1\) denklemini çözelim:
- \(35 x \equiv 1 \pmod 3\): \(35 \equiv 2 \pmod 3\) olduğundan \(2x \equiv 1 \pmod 3\); \(x_1 = 2\)’dir (\(2 \cdot 2 = 4 \equiv 1\)).
- \(21 x \equiv 1 \pmod 5\): \(21 \equiv 1 \pmod 5\) olduğundan \(x_2 = 1\)’dir.
- \(15 x \equiv 1 \pmod 7\): \(15 \equiv 1 \pmod 7\) olduğundan \(x_3 = 1\)’dir.
4. Adım.
\[ \begin{aligned} x_0 &= a_1 N_1 x_1 + a_2 N_2 x_2 + a_3 N_3 x_3 \\ &= 1 \cdot 35 \cdot 2 + 2 \cdot 21 \cdot 1 + 6 \cdot 15 \cdot 1 \\ &= 70 + 42 + 90 = 202 \end{aligned} \]
Modülo \(105\) indirgeyelim: \(202 - 105 = 97\).
\[x \equiv 97 \pmod{105}\]
(Sağlama: \(97 = 32 \cdot 3 + 1\), \(97 = 19 \cdot 5 + 2\), \(97 = 13 \cdot 7 + 6\) ✓)
\(\blacksquare\)
Örnek 16.2 (Belli Bir Aralıktaki Çözümler) \(9\), \(10\) ve \(13\) sayıları ile bölündüğünde sırasıyla \(7\), \(4\) ve \(12\) kalanını veren ve \(1 \leq x \leq 3000\) koşuluna uyan tüm \(x\) tam sayılarını bulunuz.
Çözüm
Sistem şudur:
\[x \equiv 7 \pmod 9, \qquad x \equiv 4 \pmod{10}, \qquad x \equiv 12 \pmod{13}\]
\(\gcd(9,10) = \gcd(9,13) = \gcd(10,13) = 1\) olduğundan teorem uygulanabilir.
1. Adım. \(n = 9 \cdot 10 \cdot 13 = 1170\).
2. Adım.
\[N_1 = 130, \qquad N_2 = 117, \qquad N_3 = 90\]
3. Adım.
- \(130 x \equiv 1 \pmod 9\): \(130 = 14 \cdot 9 + 4\) olduğundan \(4x \equiv 1 \pmod 9\). \(4 \cdot 7 = 28 \equiv 1 \pmod 9\) olduğundan \(x_1 = 7\)’dir.
- \(117 x \equiv 1 \pmod{10}\): \(117 \equiv 7 \pmod{10}\) olduğundan \(7x \equiv 1 \pmod{10}\). \(7 \cdot 3 = 21 \equiv 1\) olduğundan \(x_2 = 3\)’tür.
- \(90 x \equiv 1 \pmod{13}\): \(90 = 6 \cdot 13 + 12\) olduğundan \(12 x \equiv 1 \pmod{13}\). \(12 \equiv -1\) olduğundan \(-x \equiv 1\), yani \(x_3 = 12\)’dir.
4. Adım.
\[ \begin{aligned} x_0 &= 7 \cdot 130 \cdot 7 + 4 \cdot 117 \cdot 3 + 12 \cdot 90 \cdot 12 \\ &= 6370 + 1404 + 12960 \\ &= 20734 \end{aligned} \]
Modülo \(1170\) indirgeyelim: \(1170 \cdot 17 = 19890\) ve \(20734 - 19890 = 844\)’tür.
\[x \equiv 844 \pmod{1170}\]
Aralık koşulu. Çözümler \(844 + 1170t\) biçimindedir. \(1 \leq x \leq 3000\) koşulunu sağlayanlar:
- \(t = 0\): \(x = 844\)
- \(t = 1\): \(x = 2014\)
- \(t = 2\): \(x = 3184 > 3000\) ✗
O hâlde aranan sayılar \(844\) ve \(2014\)’tür.
(Sağlama: \(844 = 93 \cdot 9 + 7\), \(844 = 84 \cdot 10 + 4\), \(844 = 64 \cdot 13 + 12\) ✓)
\(\blacksquare\)
Örnek 16.3 (Katsayılı Denklemlerden Oluşan Sistem) \[5x \equiv 12 \pmod 7, \qquad 10x \equiv 4 \pmod{11}, \qquad 7x \equiv 16 \pmod{10}\]
sistemini \(1000 \leq x \leq 3000\) koşulu altında çözünüz.
Çözüm
Hazırlık: her denklemi \(x \equiv a \pmod{n}\) biçimine getirelim.
Birinci denklem. \(12 \equiv 5 \pmod 7\) olduğundan \(5x \equiv 5 \pmod 7\)’dir. \(\gcd(5,7) = 1\) olduğundan Sonuç 12.1 (1) gereği sadeleştirebiliriz:
\[x \equiv 1 \pmod 7\]
İkinci denklem. \(10 \equiv -1 \pmod{11}\) olduğundan \(-x \equiv 4\), yani
\[x \equiv -4 \equiv 7 \pmod{11}\]
Üçüncü denklem. \(16 \equiv 6 \pmod{10}\) olduğundan \(7x \equiv 6 \pmod{10}\)’dur. Her iki tarafı \(3\) ile çarpalım (\(7 \cdot 3 = 21 \equiv 1\)):
\[21x \equiv 18 \pmod{10} \implies x \equiv 8 \pmod{10}\]
Sistem şu hâle geldi:
\[x \equiv 1 \pmod 7, \qquad x \equiv 7 \pmod{11}, \qquad x \equiv 8 \pmod{10}\]
Çin kalan teoremi. \(\gcd(7,11) = \gcd(7,10) = \gcd(10,11) = 1\)’dir.
\[n = 7 \cdot 11 \cdot 10 = 770, \qquad N_1 = 110, \quad N_2 = 70, \quad N_3 = 77\]
- \(110 x \equiv 1 \pmod 7\): \(110 = 15 \cdot 7 + 5\) olduğundan \(5x \equiv 1 \pmod 7\); \(x_1 = 3\)’tür (\(15 \equiv 1\)).
- \(70 x \equiv 1 \pmod{11}\): \(70 = 6 \cdot 11 + 4\) olduğundan \(4x \equiv 1 \pmod{11}\); \(x_2 = 3\)’tür (\(12 \equiv 1\)).
- \(77 x \equiv 1 \pmod{10}\): \(77 \equiv 7 \pmod{10}\) olduğundan \(7x \equiv 1 \pmod{10}\); \(x_3 = 3\)’tür (\(21 \equiv 1\)).
Şimdi toplayalım:
\[ \begin{aligned} x_0 &= 1 \cdot 110 \cdot 3 + 7 \cdot 70 \cdot 3 + 8 \cdot 77 \cdot 3 \\ &= 330 + 1470 + 1848 \\ &= 3648 \end{aligned} \]
Modülo \(770\): \(770 \cdot 4 = 3080\) ve \(3648 - 3080 = 568\)’dir.
\[x \equiv 568 \pmod{770}\]
Aralık koşulu. Çözümler \(568 + 770t\) biçimindedir:
- \(t = 1\): \(x = 1338\)
- \(t = 2\): \(x = 2108\)
- \(t = 3\): \(x = 2878\)
- \(t = 4\): \(x = 3648 > 3000\) ✗
Aranan sayılar \(1338\), \(2108\) ve \(2878\)’dir.
\(\blacksquare\)
16.3 Modüller Aralarında Asal Değilse
Çin kalan teoremi modüllerin ikişer ikişer aralarında asal olmasını istiyordu. Bu koşul sağlanmadığında sistem çözülebilir de olabilir, olmayabilir de. Aşağıdaki teorem iki denklemli durumda ölçütü tam olarak verir.
Teorem 16.2 (Aralarında Asal Olmayan Modüller) \(a, b, n, m \in \mathbb{Z}\) ve \(1 < n, m\) olsun.
\[x \equiv a \pmod n, \qquad x \equiv b \pmod m\]
sisteminin bir ortak çözümünün olması için gerek ve yeter koşul
\[\gcd(n, m) \ \mid \ a - b\]
olmasıdır. Sistem çözülebilirse, çözüm \(\operatorname{lcm}(n, m)\) modülüne göre tek türlü belirlidir.
İspat
Çözülebilirlik. \(x\) bir ortak çözüm olsun. Birinci denklem gereği \(x = a + nu\), ikinci denklem gereği \(x = b + mv\) olacak biçimde \(u, v\) tam sayıları vardır. İkisini eşitleyelim:
\[a + nu = b + mv \implies nu - mv = b - a\]
Demek ki sistemin çözülebilir olması, \(nu - mv = b - a\) Diofant denkleminin çözülebilir olmasına denktir. Teorem 8.1 (1) ve Önerme 4.2 (3) gereği bu denklem çözülebilirdir ancak ve ancak
\[\gcd(n, -m) = \gcd(n, m) \ \mid \ b - a\]
ise. \(\gcd(n,m) \mid b-a\) ile \(\gcd(n,m) \mid a-b\) aynı koşuldur.
Teklik. \(x_0\) ile \(x_1\) iki ortak çözüm olsun. Her iki denklemden
\[n \mid x_0 - x_1 \qquad \text{ve} \qquad m \mid x_0 - x_1\]
çıkar; yani \(x_0 - x_1\) sayısı \(n\) ile \(m\)’nin ortak katıdır. Sonuç 7.1 gereği
\[\operatorname{lcm}(n,m) \ \mid \ x_0 - x_1\]
olur; yani \(x_0 \equiv x_1 \pmod{\operatorname{lcm}(n,m)}\)’dir.
\(\blacksquare\)
\(\gcd(n,m) = 1\) olduğunda ölçüt kendiliğinden sağlanır (çünkü \(1\) her sayıyı böler) ve
\[\operatorname{lcm}(n,m) = \frac{nm}{\gcd(n,m)} = nm\]
olur. Yani Teorem 16.2, iki denklemli durumda Çin kalan teoremini kapsar.
Örnek 16.4 (Ortak Bölenli Modüller) Aşağıdaki sistemlerin çözülebilir olup olmadığını belirleyiniz; çözülebilenleri çözünüz.
a) \(x \equiv 3 \pmod 8\) ve \(x \equiv 7 \pmod{12}\)
b) \(x \equiv 3 \pmod 8\) ve \(x \equiv 6 \pmod{12}\)
Çözüm
Her iki şıkta da \(\gcd(8, 12) = 4\) ve \(\operatorname{lcm}(8,12) = 24\)’tür.
a) \(a - b = 3 - 7 = -4\) ve \(4 \mid -4\) olduğundan sistem çözülebilirdir.
Birinci denklemden \(x = 3 + 8u\) yazıp ikincide yerine koyalım:
\[3 + 8u \equiv 7 \pmod{12} \implies 8u \equiv 4 \pmod{12}\]
\(\gcd(8,12) = 4\) ve \(4 \mid 4\) olduğundan çözülebilir; denklemi \(4\)’e bölelim:
\[2u \equiv 1 \pmod 3\]
\(2 \equiv -1 \pmod 3\) olduğundan \(-u \equiv 1\), yani \(u \equiv -1 \equiv 2 \pmod 3\)’tür. Buradan \(u = 2 + 3s\) ve
\[x = 3 + 8(2 + 3s) = 19 + 24 s\]
O hâlde
\[x \equiv 19 \pmod{24}\]
(Sağlama: \(19 = 2 \cdot 8 + 3\) ✓ ve \(19 = 12 + 7\) ✓)
b) \(a - b = 3 - 6 = -3\) ve \(4 \nmid -3\) olduğundan Teorem 16.2 gereği sistemin hiç çözümü yoktur.
Sezgisel açıklama: birinci denklem \(x\)’in tek olmasını gerektirir (çünkü \(3 + 8u\) daima tektir), ikincisi ise çift olmasını (çünkü \(6 + 12v\) daima çifttir).
\(\blacksquare\)
16.4 Çalışma Problemleri
Alıştırma 16.1 (Kongrüans Sistemleri) Aşağıdaki sistemleri çözünüz.
a) \(x \equiv 2 \pmod 3\), \(x \equiv 3 \pmod 5\), \(x \equiv 2 \pmod 7\)
b) \(x \equiv 5 \pmod{11}\), \(x \equiv 14 \pmod{29}\), \(x \equiv 15 \pmod{31}\)
c) \(3x \equiv 1 \pmod 4\), \(4x \equiv 3 \pmod 5\), \(5x \equiv 2 \pmod 7\)
Alıştırma 16.2 (Bir Uygulama) Bir sepetteki yumurtalar \(3\)’erli sayıldığında \(2\), \(5\)’erli sayıldığında \(3\), \(7\)’şerli sayıldığında \(2\) yumurta artmaktadır. Sepette en az kaç yumurta vardır?
Alıştırma 16.3 (Ortak Bölenli Modüller) Aşağıdaki sistemlerin çözülebilirliğini Teorem 16.2 ile inceleyiniz; çözülebilenleri çözünüz.
a) \(x \equiv 4 \pmod 6\) ve \(x \equiv 10 \pmod{15}\)
b) \(x \equiv 1 \pmod 4\) ve \(x \equiv 2 \pmod 6\)
c) \(x \equiv 5 \pmod{12}\) ve \(x \equiv 11 \pmod{18}\)
Alıştırma 16.4 (Üç Denkleme Genelleme) \(n_1, n_2, n_3\) modülleri ikişer ikişer aralarında asal olmasa bile,
\[x \equiv a_i \pmod{n_i} \qquad (i = 1,2,3)\]
sisteminin çözülebilir olması için gerek ve yeter koşulun
\[\gcd(n_i, n_j) \ \mid \ a_i - a_j \qquad (\text{her } i \neq j \text{ için})\]
olduğunu gösteriniz.
İpucu: İlk iki denklemi Teorem 16.2 ile birleştirip tek bir kongrüansa indirgeyiniz, sonra üçüncüyle aynı işlemi tekrarlayınız.