En küçük çözüm
Modül
Modüller

    Denklemler

    Çin kalan teoremi hakkında daha fazlası

    Çin kalan teoremi çözücü

    Bir yığın nesneyi üçer üçer sayın, 2 artar; beşer beşer sayın, 3 artar; yedişer yedişer sayın, 2 artar: 23 tane vardır, ya da 128, ya da 233; her 105'te bir cevap. Bu, Çin kalan teoremine adını veren Sunzi Suanjing problemidir. İstediğiniz kadar denklem ve istediğiniz büyüklükte sayılarla herhangi bir x ≡ a (mod n) denklik sistemi yazın; cevabı, sizin sayılarınızla çözüm yolunu ve neden işe yaradığını gösteren bir görseli görün. Denklemlerin hepsi birden sağlanamıyorsa çözücü çelişen iki denklemi söyler ve nedenini gösterir. x ≡ a (mod n) denklemlerini her satıra bir tane olacak şekilde yazın: a kalan, n ise modüldür. Denklem ekle ile ya da son modülde Enter tuşuyla satır ekleyin, × ile satır silin. 200 basamağa kadar tam sayılar çalışır ve a negatif olabilir. Ya da çözümlü bir örnek seçin. Kutucuklar en küçük çözümü ve kaçta bir tekrarlandığını gösterir; altında ilk pozitif çözümler ve her denklemin sağlaması yer alır. Görsel, her denklemi sağlayan sayıları işaretler; her satırda işareti olan sütun çözümdür. Kalan tablosu iki denklemi birlikte gösterir. Çözüm yolu sizin sayılarınızla, ders kitabındaki kurulumla ya da yerine koyma yöntemiyle yazılır.

    Nasıl çalışır

    1. x ≡ a (mod n) denklemlerini her satıra bir tane yazın ya da Sunzi'nin problemi, yumurta sepeti veya Jülyen dönemi gibi çözümlü bir örnek seçin.
    2. En küçük çözümü, tekrarlandığı modülü ve her biri tüm denklemlerle sağlanmış ilk pozitif çözümleri okuyun.
    3. Çözüm yolunu kurulumla ya da yerine koyma yöntemiyle adım adım izleyin ve görseli sayı doğrusu ile kalan tablosu arasında değiştirin.

    Kurulum nasıl işler

    Hiçbir iki modülün ortak çarpanı yoksa çözüm doğrudan kurulabilir. Modülleri çarpın: Sunzi'nin probleminde N = 3 × 5 × 7 = 105. Her denklem için diğer tüm modüllerin katı olan Nᵢ = N / nᵢ'yi alın: 35, 21 ve 15. Sonra genişletilmiş Öklid algoritmasıyla Nᵢ'nin mod nᵢ'ye göre tersi yᵢ'yi bulun: 35, 3'e bölündüğünde 2 kalanını verir ve 2 × 2 = 4 ≡ 1 (mod 3) olduğundan y₁ = 2; 21 ve 15 kalan olarak 1 verir, dolayısıyla tersleri 1'dir. Şimdi x = 2 × 35 × 2 + 3 × 21 × 1 + 2 × 15 × 1 = 233 ve 233 mod 105 = 23. Her terim kendi denklemine uyar ve diğer modüllerin katıdır; bu yüzden toplam hepsine uyar.

    Modüllerin ortak çarpanı olduğunda

    Modülleri ortak çarpanlara sahip bir sistemin de çözümü olabilir. x ≡ a (mod m) ve x ≡ b (mod n) denklemleri, tam olarak a − b sayısı gcd(m, n)'nin katı olduğunda aynı anda sağlanabilir ve çözüm o zaman her m × n yerine her lcm(m, n)'de bir tekrarlanır. 5. ve 11. dakikada, her 12 ve her 18 dakikada bir kalkan iki otobüs 29. dakikada ve ondan sonra her 36 dakikada bir buluşur, çünkü 11 − 5 = 6, gcd(12, 18) = 6'nın katıdır. Ama x ≡ 1 (mod 4) ve x ≡ 4 (mod 6) asla birlikte sağlanamaz: ilki x'i tek, ikincisi çift yapar. Bütün bir sistemin çözümü, tam olarak denklemlerinin her çiftinin çözümü olduğunda vardır; çözücü çelişen iki denklemi böyle bulur.

    Sık sorulan sorular

    Çin kalan teoremi ne der?

    n₁, n₂, … modüllerinin hiçbir ikisinin ortak çarpanı yoksa, herhangi a₁, a₂, … kalanları için her i'de x ≡ aᵢ (mod nᵢ) olan, 0 ile N − 1 arasında tam olarak bir x vardır; burada N modüllerin çarpımıdır. Diğer her çözüm bundan N'nin bir katı kadar farklıdır: Sunzi'nin probleminde çözümler 23, 128, 233 ve böyle devam eder, her 105'te bir tane.

    Neden Çin teoremi deniyor?

    Bu türden bilinen en eski problem, 3. ile 5. yüzyıllar arasında yazılmış Çince bir aritmetik kitabı olan Sunzi Suanjing'de yer alır: üçer, beşer ve yedişer sayıldığında bir miktar nesne 2, 3 ve 2 kalanlarını verir. Qin Jiushao bu tür problemler için 1247'de genel bir yöntem verdi; Carl Friedrich Gauss da teoremi 1801'de bugünkü biçimiyle ifade etti.

    Modüller aralarında asal değilse ne olur?

    O zaman çözüm olmayabilir; varsa da her çarpımda bir değil, modüllerin her en küçük ortak katında bir tekrarlanır. İki denklem, kalanları modüllerinin gcd'sine göre eşit olduğunda uyuşur. Yumurta bilmecesi ortak çarpanları olan 2, 3, 4, 5, 6 ve 7'yi kullanır ve yine de bir çözümü vardır: her 420'de bir tekrarlanan 301.

    RSA, Çin kalan teoremini nasıl kullanır?

    Bir RSA mesajını çözmek, n = p × q iken c^d mod n'yi hesaplamak demektir. c^d mod p ve c^d mod q'yu, üssü mod p − 1 ve q − 1'e göre indirgenmiş olarak ayrı ayrı hesaplamak ve iki sonucu teoremle birleştirmek daha hızlıdır. Yarı uzunluktaki sayılarla iki kuvvetin her biri işin yaklaşık sekizde birini gerektirir; bu yüzden şifre çözme yaklaşık dört kat hızlanır ve çoğu RSA yazılımı bu şekilde çalışır.

    Sayılar ne kadar büyük olabilir?

    Her biri en fazla 200 basamaklı sayılarla 20 denkleme kadar. Çözücü tarayıcınızda kesin tam sayılarla çalışır; cevap ne kadar uzun olursa olsun kesindir ve hiçbir şey hiçbir yere gönderilmez.

    Denemeye hazır mısınız?

    PictorX'i tarayıcınızda açın — kurulum gerekmez, başlamak için kredi kartı gerekmez.

    Editöre Git