Çin Kalan Teoremi nedir?
Çin Kalan Teoremi (ÇKT), sayılar teorisinin klasik sonuçlarından biridir. Bu teoreme göre, \(x \equiv a_1 \pmod{m_1}\), \(x \equiv a_2 \pmod{m_2}\), … şeklinde bir kongrüans sisteminiz varsa ve modüller ikişerli aralarında asal ise (ortak çarpanları yoksa), bu sistemin \(M = m_1 \cdot m_2 \cdot \ldots\) modülüne göre tek bir çözümü vardır. Bu hesaplayıcı, söz konusu en küçük negatif olmayan çözümü bulur.
Hesaplayıcı nasıl kullanılır?
Her kalan \(a_i\) değerini, kendi modülü \(m_i\) ile birlikte girin. İki ya da üç kongrüanstan oluşan bir sistemi çözebilirsiniz; yalnızca iki kongrüansa ihtiyacınız varsa üçüncü modülü boş bırakın. Araç, modüllerinizin ikişerli aralarında asal olup olmadığını denetler ve ardından \(x\) ile birleşik modül \(M\)'yi döndürür. Herhangi bir tam sayı \(k\) için \(x + Mk\) biçimindeki tüm değerler de birer çözümdür.
Formülün açıklaması
\(M = \prod m_i\) olsun. Her kongrüans için \(M_i = M / m_i\) ve \(y_i = M_i^{-1} \bmod m_i\) tanımlanır (modüler ters, genişletilmiş Öklid algoritmasıyla hesaplanır). Çözüm, ağırlıklı toplam olarak $$x \equiv \sum_{i} a_i\,M_i\,y_i \pmod{M}$$ şeklinde verilir. \(M_i\), \(m_i\) dışındaki tüm modüllere bölünebildiği için her terim yalnızca kendi kongrüansına doğru kalanı katar.
Çözümlü örnek
\(x \equiv 2 \pmod{3}\) ve \(x \equiv 1 \pmod{4}\) sistemini çözelim. Burada \(M = 3 \cdot 4 = 12\)'dir. \(M_1 = 4\) olup \(4 \equiv 1 \pmod{3}\) olduğundan \(y_1 = 1\); \(M_2 = 3\) olup \(3 \equiv 3 \pmod{4}\) olduğundan \(y_2 = 3\) (çünkü \(3 \cdot 3 = 9 \equiv 1\)). Buradan $$x = 2 \cdot 4 \cdot 1 + 1 \cdot 3 \cdot 3 = 8 + 9 = 17 \equiv 5 \pmod{12}$$ bulunur. Doğrulama: \(5 \bmod 3 = 2\) ✓ ve \(5 \bmod 4 = 1\) ✓.
Sıkça Sorulan Sorular
Modüller neden aralarında asal olmalı? İki modül ortak bir çarpana sahipse, sistemin hiç çözümü olmayabilir ya da bunların en küçük ortak katı (ekok) modülüne göre birden fazla çözümü olabilir; bu durumda standart ÇKT formülü geçerliliğini yitirir.
"En küçük negatif olmayan çözüm" ne demek? Tüm çözümler birbirinden \(M\)'nin katları kadar farklıdır; hesaplayıcı bunlardan \(0\) ile \(M-1\) aralığında olanı verir.
Negatif kalan kullanabilir miyim? Evet. Bu değerler çözümden önce her \(m_i\) modülüne göre \(0\) ile \(m_i-1\) aralığına indirgenir.
