Çin Kalan Teoremi Hesaplayıcı

Q: Formülü kullanmadan bir ÇKT sistemini elle nasıl çözebilirim?

İki kongrüans için yerine koyma yöntemini kullanabilirsiniz: ilkinden x = a₁ + k·n₁ olur; burada k tam sayıdır. Bunu ikinci kongrüansa yerleştirin: a_1 + k n_1 equiv a_2 ±odn_2; n_1'in n_2 moduna göre tersini bularak k'yı çözün. Sonra k'yı geri yerleştirip x'i bulun ve n_1 n_2 moduna göre indirgeyin. Bu ardışık yerine koyma yöntemi, kongrüansları ikişer ikişer çözerek her sayıda kongrüans için iş görür.

Q: Modlar ikili aralarında asal değilse ne olur?

İki mod ortak bir çarpan paylaştığında sistem tutarsız olabilir ve hiç çözümü olmayabilir. Bir çözüm ancak kalanlar uyumluysa vardır: her çift için a_i equiv a_j ±odgcd(n_i, n_j). Uyumlularsa çözüm yine tektir, ancak modların çarpımı yerine en küçük ortak katları moduna göredir. Aralarında asallık koşulu, çözümün her zaman var olmasını garanti eder; bu yüzden bu hesaplayıcı böyle girişleri reddeder.

Q: Çözüm neden tektir ve diğer tüm çözümleri nasıl bulurum?

x ve x' gibi iki sayı da sistemi sağlıyorsa, farkları her modla bölünür; dolayısıyla (aralarında asal olduklarından) çarpımları N ile bölünür. O hâlde x equiv x' ±odN olur; yani 0 ≤ x < N aralığında tam olarak bir çözüm vardır. Diğer tüm çözümler herhangi bir tam sayı k için x + kN biçimindedir; probleminiz izin veriyorsa x - N gibi negatif değerler de buna dahildir.

Q: Kalanlar negatif veya moddan büyük olabilir mi?

Evet. Modundan büyük bir kalan otomatik olarak indirgenir — örneğin n = 5 ile a = 7, a = 2 ile aynıdır. Negatif kalanlar da çalışır: x equiv -1 ±od5, x equiv 4 ±od5 ile aynı anlama gelir. Nihai cevap her zaman 0 ≤ x < N aralığındaki en küçük negatif olmayan temsilciye normalize edilir.

Q: Modüler tersi elle nasıl bulabilirim?

Genişletilmiş Öklid algoritmasını kullanın: N_i ve n_i üzerine sıradan Öklid algoritmasını uygulayın, sonra geriye doğru çalışarak gcd = 1'i uN_i + vn_i biçiminde yazın. u katsayısı uN_i equiv 1 ±odn_i koşulunu sağlar, dolayısıyla y_i = u bmod n_i. Asal bir mod p için Fermat'nın Küçük Teoremi'ni de kullanabilirsiniz: y_i equiv N_i^p-2 ±odp.

Q: Çin Kalan Teoremi kullanılırken sık yapılan hatalar nelerdir?

En sık yapılan hatalar şunlardır: modların ikili aralarında asal olmaması (örneğin 2 çarpanını paylaşan 4 ve 6); veri girerken kalan ve mod alanlarının karıştırılması; cevabın tek bir sayı değil bir çözüm sınıfı olduğunun unutulması; ve teknik olarak izin verilen ama hiçbir bilgi eklemeyen 1 modunun girilmesi. Ayrıca kalanlarınızın probleminize uyduğunu kontrol edin — x equiv 2 ±od3 ile x equiv 3 ±od2 aynı şey değildir.

Q: Hesaplayıcının cevabını hızlıca doğrulamanın bir yolu var mı?

Evet — cevabı her modla bölüp kalanları kontrol etmeniz yeterlidir. Sonuç x ise, sisteminizdeki her kongrüans için x bmod n_i = a_i bmod n_i olduğunu doğrulayın. İkinci bir denetim: x bmod N değerini, örneğin ardışık yerine koyma gibi farklı bir yöntemle hesaplayıp aynı değeri aldığınızı teyit edin. Her iki denetim de geçerse çözüm doğrudur, çünkü N moduna göre teklilik, aralıkta başka bir cevap olmadığını garanti eder.

Güncellendi: 3 Ekim 2026

Çin Kalan Teoremi'ni kullanarak eşzamanlı kongrüanslar sistemini çözer. En küçük negatif olmayan çözümü elde etmek için kalanları ve ikili aralarında asal modları girin.

Çin Kalan Teoremi Çözücü

Çin Kalan Teoremi Formülü

Formül

\[ x \equiv a_1 \pmod{n_1} \\ x \equiv a_2 \pmod{n_2} \\ \vdots \\ x \equiv a_k \pmod{n_k} \\[1.5em] N = n_1 \cdot n_2 \cdots n_k, \quad N_i = \frac{N}{n_i}, \quad y_i \equiv N_i^{-1} \pmod{n_i} \\[1.5em] x \equiv \sum_{i=1}^{k} a_i \, N_i \, y_i \pmod{N} \]

Burada:

\(a_i\) — kalanlar (\(x\)'in kongrüant olması gereken değerler)
\(n_i\) — modlar; ikili aralarında asal olmalıdırlar (herhangi ikisinin en büyük ortak böleni 1'dir)
\(N\) — tüm modların çarpımı; modlar aralarında asal olduğunda bunların en küçük ortak katına eşittir
\(N_i\) — \(n_i\) dışındaki tüm modların çarpımı
\(y_i\) — \(N_i\)'nin \(n_i\) moduna göre modüler tersi; yani \(N_i y_i \equiv 1 \pmod{n_i}\) olan sayı
\(x\) — \(N\) moduna göre tek çözüm

Teorem, modlar ikili aralarında asal olduğunda sistemin \(0 \le x < N\) aralığında tam olarak bir çözümü olduğunu söyler. Formül, bu çözümü her bir kalanı ilgili kısmi çarpımın tersiyle birleştirerek oluşturur.

Çin Kalan Teoremi – Hesaplama Örneği

Örnek: \(x \equiv 2 \pmod{3}\) ve \(x \equiv 3 \pmod{5}\) koşullarını sağlayan \(x\)'i bulun — bunlar hesaplayıcının varsayılan değerleridir.

\[ N = 3 \times 5 = 15 \]

\[ N_1 = \frac{15}{3} = 5, \quad y_1 = 2 \; (\text{çünkü } 5 \cdot 2 = 10 \equiv 1 \pmod{3}) \]

\[ N_2 = \frac{15}{5} = 3, \quad y_2 = 2 \; (\text{çünkü } 3 \cdot 2 = 6 \equiv 1 \pmod{5}) \]

\[ x \equiv (2 \cdot 5 \cdot 2) + (3 \cdot 3 \cdot 2) \pmod{15} \equiv 20 + 18 = 38 \equiv 8 \pmod{15} \]

Sonuç: \(x = 8\) (mod \(15\)). Gerçekten de \(8 \div 3 = 2\) olup kalan \(2\), ve \(8 \div 5 = 1\) olup kalan \(3\)'tür; dolayısıyla her iki kongrüans da sağlanır. Bir sonraki çözüm \(8 + 15 = 23\), ardından \(38\) ve böylece sürer.

Hesaplayıcı Nasıl Kullanılır?

Kongrüans sayısını girin (en az 2). Yeni kalan/mod çiftleri otomatik olarak görünür.
İlk kongrüans için kalanı kalan 1 (\(a_1\)) alanına, modu mod 1 (\(n_1\)) alanına yazın.
Aynı işlemi kalan 2 / mod 2 ve varsa diğer çiftler için tekrarlayın.
En küçük negatif olmayan çözüm \(x\)'i ve Mod (modların EKOK'u) \(N\)'yi okuyun. \(x + kN\) (\(k = 0, 1, 2, \dots\)) biçimindeki her sayı da sistemi sağlar.

Çin Kalan Teoremi Nedir?

Çin Kalan Teoremi (ÇKT), sayılar teorisinin klasik bir sonucudur ve ilk olarak MS 3.–5. yüzyıllar arasında Çinli matematikçi Sunzi tarafından tanımlanmıştır. Teorem şu soruyu yanıtlar: birkaç bölen ile bilinmeyen bir sayının bunlara bölünmesinden kalan kalanlar verildiğinde, o sayı geri bulunabilir mi? Teoremin yanıtı evettir — modlar ikili aralarında asal olduğu sürece — ve cevap, uzunluğu tüm modların çarpımı olan bir aralık içinde tektir.

Bunu somutlaştırmanın bir yolu: bir yumurta sepetinde \(x\) yumurta varsa ve 3'erli sayınca 2 artıyorsa, 5'erli sayınca da 3 artıyorsa, \(x \equiv 2 \pmod{3}\) ve \(x \equiv 3 \pmod{5}\) olur. ÇKT, \(x\)'i mod 15'e göre tek biçimde belirler — bu örnekte \(x = 8, 23, 38, \dots\)

Teoremin önemi, birçok küçük kongrüanslık sisteminin büyük modlu tek bir kongrüansa denk olduğunu göstermesinden gelir. Bu sayede çok büyük bir modla yapılan aritmetik, birkaç küçük ve kullanışlı modla yapılan paralel aritmetikle değiştirilebilir ve sonuçlar sonra yeniden birleştirilebilir. Birleştirme adımı modüler tersleri kullanır; bunları Çarpımsal Mod Tersi hesaplayıcısıyla ayrıca hesaplayabilirsiniz; bu tür tersler ayrıca Fermat'nın Küçük Teoremi ve Euler Teoremi ile de ilgilidir.

Sonucun Yorumlanması

Hesaplayıcı en küçük negatif olmayan çözüm \(x\)'i ve birleşik mod \(N\)'yi verir. Tam çözüm kümesi \(x, x + N, x + 2N, \dots\) biçimindedir; probleminizde negatif cevaplar anlamlıysa \(x - N\) ve daha küçük değerler de geçerlidir. Çözüm \(N\) moduna göre tek olduğundan, aynı \(x \pmod{N}\) değerini üreten iki farklı giriş tam olarak aynı sistemi tanımlar.

Varsayımlar ve Sınırlamalar

Modların ikili aralarında asal olması gerekir. Her mod çifti 1'den büyük ortak bir çarpan paylaşmamalıdır; aksi hâlde hesaplayıcı hata bildirir. Örneğin iki mod 4 ve 6 ise (ikisi de 2 ile bölünebilir), sistemin hiç çözümü olmayabilir ya da EKOK'ları moduna göre birden çok çözüm bulunabilir.
Sistemin tutarlılığı. Modlar aralarında asal olduğunda teorem her zaman bir çözüm verir — ÇKT'nin gücü budur. Kongrüanslar arasındaki çelişkiler yalnızca aralarında asallık koşulu bozulduğunda ortaya çıkabilir.
Kalanlar moddan büyük olabilir. \(a = 7, n = 5\) gibi bir giriş \(7 \equiv 2 \pmod 5\) olarak ele alınır; hesaplayıcı nihai cevabı otomatik olarak \(N\) moduna göre indirger.
Modlar pozitif tam sayı olmalıdır. 0 veya negatif değerler reddedilir.
Büyük sistemler. \(N\) tüm modların çarpımı olduğundan çok hızlı büyür. Çok sayıda mod varsa, söz konusu sayılar standart kayan nokta aritmetiğinin tam olarak çalıştığı aralığı aşabilir.

ÇKT Nerede Kullanılır?

Saf sayılar teorisinin ötesinde ÇKT, birkaç alanda etkin bir araçtır. Kriptografide, sonucu her asal çarpan moduna ayrı ayrı hesaplayıp birleştirerek RSA şifre çözümünü hızlandırır; ayrıca Shamir'in Gizli Paylaşımı gibi eşik şemalarının temelini oluşturur. Bilgisayar biliminde, küçük modlar üzerinde toplama ve çarpma işlemlerini paralel olarak gerçekleştiren rezidü (kalan) sayı sistemlerini olanaklı kılar; ayrıca hashing, çizelgeleme ve takvim hesaplarında karşımıza çıkar — Sunzi'nin çalışmalarına ilk ilhamı veren klasik "askerleri sıralara göre sayma" problemleri.

Sıkça Sorulan Sorular

Formülü kullanmadan bir ÇKT sistemini elle nasıl çözebilirim?

İki kongrüans için yerine koyma yöntemini kullanabilirsiniz: ilkinden x = a₁ + k·n₁ olur; burada \(k\) tam sayıdır. Bunu ikinci kongrüansa yerleştirin: \(a_1 + k n_1 \equiv a_2 \pmod{n_2}\); \(n_1\)'in \(n_2\) moduna göre tersini bularak \(k\)'yı çözün. Sonra \(k\)'yı geri yerleştirip \(x\)'i bulun ve \(n_1 n_2\) moduna göre indirgeyin. Bu ardışık yerine koyma yöntemi, kongrüansları ikişer ikişer çözerek her sayıda kongrüans için iş görür.

Modlar ikili aralarında asal değilse ne olur?

İki mod ortak bir çarpan paylaştığında sistem tutarsız olabilir ve hiç çözümü olmayabilir. Bir çözüm ancak kalanlar uyumluysa vardır: her çift için \(a_i \equiv a_j \pmod{\gcd(n_i, n_j)}\). Uyumlularsa çözüm yine tektir, ancak modların çarpımı yerine en küçük ortak katları moduna göredir. Aralarında asallık koşulu, çözümün her zaman var olmasını garanti eder; bu yüzden bu hesaplayıcı böyle girişleri reddeder.

Çözüm neden tektir ve diğer tüm çözümleri nasıl bulurum?

\(x\) ve \(x'\) gibi iki sayı da sistemi sağlıyorsa, farkları her modla bölünür; dolayısıyla (aralarında asal olduklarından) çarpımları \(N\) ile bölünür. O hâlde \(x \equiv x' \pmod{N}\) olur; yani \(0 \le x < N\) aralığında tam olarak bir çözüm vardır. Diğer tüm çözümler herhangi bir tam sayı \(k\) için \(x + kN\) biçimindedir; probleminiz izin veriyorsa \(x - N\) gibi negatif değerler de buna dahildir.

Kalanlar negatif veya moddan büyük olabilir mi?

Evet. Modundan büyük bir kalan otomatik olarak indirgenir — örneğin \(n = 5\) ile \(a = 7\), \(a = 2\) ile aynıdır. Negatif kalanlar da çalışır: \(x \equiv -1 \pmod{5}\), \(x \equiv 4 \pmod{5}\) ile aynı anlama gelir. Nihai cevap her zaman \(0 \le x < N\) aralığındaki en küçük negatif olmayan temsilciye normalize edilir.

Modüler tersi elle nasıl bulabilirim?

Genişletilmiş Öklid algoritmasını kullanın: \(N_i\) ve \(n_i\) üzerine sıradan Öklid algoritmasını uygulayın, sonra geriye doğru çalışarak \(\gcd = 1\)'i \(uN_i + vn_i\) biçiminde yazın. \(u\) katsayısı \(uN_i \equiv 1 \pmod{n_i}\) koşulunu sağlar, dolayısıyla \(y_i = u \bmod n_i\). Asal bir mod \(p\) için Fermat'nın Küçük Teoremi'ni de kullanabilirsiniz: \(y_i \equiv N_i^{p-2} \pmod{p}\).

Çin Kalan Teoremi kullanılırken sık yapılan hatalar nelerdir?

En sık yapılan hatalar şunlardır: modların ikili aralarında asal olmaması (örneğin 2 çarpanını paylaşan 4 ve 6); veri girerken kalan ve mod alanlarının karıştırılması; cevabın tek bir sayı değil bir çözüm sınıfı olduğunun unutulması; ve teknik olarak izin verilen ama hiçbir bilgi eklemeyen 1 modunun girilmesi. Ayrıca kalanlarınızın probleminize uyduğunu kontrol edin — \(x \equiv 2 \pmod{3}\) ile \(x \equiv 3 \pmod{2}\) aynı şey değildir.

Hesaplayıcının cevabını hızlıca doğrulamanın bir yolu var mı?

Evet — cevabı her modla bölüp kalanları kontrol etmeniz yeterlidir. Sonuç \(x\) ise, sisteminizdeki her kongrüans için \(x \bmod n_i = a_i \bmod n_i\) olduğunu doğrulayın. İkinci bir denetim: \(x \bmod N\) değerini, örneğin ardışık yerine koyma gibi farklı bir yöntemle hesaplayıp aynı değeri aldığınızı teyit edin. Her iki denetim de geçerse çözüm doğrudur, çünkü \(N\) moduna göre teklilik, aralıkta başka bir cevap olmadığını garanti eder.