Çin kalan teoremi açıklaması

Bir sayı 3'e bölündüğünde 2, 5'e bölündüğünde 3 ve 7'ye bölündüğünde 2 kalanını veriyor. Bu sayı hangisi? Sayıları tek tek denerseniz bir süre sonra 23'e ulaşırsınız, ama sorunun içinde bir teorem saklı: bölenlerin ortak çarpanı olmadığı sürece, çarpımlarının altında her zaman tam olarak bir cevap vardır ve hiçbir şey denemeden bulunur. Teorem yaklaşık 1.500 yaşındadır ve takvimlerde, bilgisayar aritmetiğinde ve web'i koruyan kriptografide hâlâ iş başındadır.

2 mod 3, 3 mod 5 ve 2 mod 7 kalanını veren sayılar için üç sıra işaret; tek bir sütunda 23'te buluşuyorlar
2 mod 3, 3 mod 5 ve 2 mod 7 kalanını veren sayılar için üç sıra işaret; tek bir sütunda 23'te buluşuyorlar

Sunzi Suanjing'den bir problem

3. ile 5. yüzyıllar arasından Çince bir aritmetik kitabı olan Sunzi Suanjing, üçer üçer sayılınca 2, beşer beşer sayılınca 3 ve yedişer yedişer sayılınca 2 artan bir miktar nesneyi sorar. Cevabı 23'tür ve yöntemi bugün hâlâ öğretilen yöntemdir: üçer sayarken artan her nesne için 70, beşer sayarken artan her nesne için 21 ve yedişer sayarken artan her nesne için 15 alın, toplayın ve mümkün olduğu kadar 105 çıkarın. 2 × 70 + 3 × 21 + 2 × 15 = 233 ve 233 − 2 × 105 = 23. Ming döneminden bir dize, 70, 21, 15 ve 105 sayılarını yüzyıllarca akılda tuttu. Qin Jiushao 1247'de genel bir yöntem verdi, aynı problem Fibonacci'nin 1202 tarihli Liber Abaci'sinde de yer alır ve Carl Friedrich Gauss teoremi 1801 tarihli Disquisitiones Arithmeticae'sinde bugünkü biçimiyle ifade etti.

Sunzi Suanjing’in bir Qing dönemi baskısından bir sayfa. 3.–5. yüzyıl Çin aritmetik kitabı, üçer, beşer ve yedişer sayıldığında 2, 3 ve 2 kalan bir sayı ister.
Sunzi Suanjing’in bir Qing dönemi baskısından bir sayfa. 3.–5. yüzyıl Çin aritmetik kitabı, üçer, beşer ve yedişer sayıldığında 2, 3 ve 2 kalan bir sayı ister.
Carl Friedrich Gauss, Christian Albrecht Jensen’in 1840 tarihli portresinde. a ≡ b (mod n) kongrüans gösterimini 1801’deki Disquisitiones Arithmeticae’de ortaya koydu.
Carl Friedrich Gauss, Christian Albrecht Jensen’in 1840 tarihli portresinde. a ≡ b (mod n) kongrüans gösterimini 1801’deki Disquisitiones Arithmeticae’de ortaya koydu.

Teorem ne der

Hiçbir ikisinin ortak çarpanı olmayan n₁, n₂, …, nₖ modüllerini ve herhangi a₁, a₂, …, aₖ kalanlarını alın. O zaman N = n₁ × n₂ × … × nₖ olmak üzere, her i için nᵢ'ye bölündüğünde aᵢ kalanını veren, 0 ile N − 1 arasında tam olarak bir x tam sayısı vardır. Diğer tüm çözümler bundan N'nin bir katı kadar farklıdır. Modüler aritmetik gösterimiyle: x ≡ aᵢ (mod nᵢ) sisteminin bir çözümü vardır ve bu çözüm mod N'ye göre tektir. Başka bir deyişle, 0 ile N − 1 arasındaki bir sayı ile kalanlarının listesi tam olarak aynı bilgiyi taşır: 3 × 5 × 7 = 105 sayı ve 3 × 5 × 7 = 105 olası kalan listesi, her biri bir kez kullanılır.

Çözümü kurmak

70, 21 ve 15 sayıları sihirli değildir. Her biri kendi modülüne bölündüğünde 1, diğerlerine bölündüğünde 0 kalanını verir: 70 = 2 × 35, 5'in ve 7'nin katıdır ve 3'e bölündüğünde 1 kalanını verir. Genel olarak nᵢ dışındaki her modülün katı olan Nᵢ = N / nᵢ alınır ve Nᵢ'nin mod nᵢ'ye göre tersi olan yᵢ ile çarpılır. Ters vardır, çünkü Nᵢ ile nᵢ'nin ortak çarpanı yoktur; genişletilmiş Öklid algoritması da onu bulur: en büyük ortak bölen için Öklid bölmelerini yapar ve geriye doğru Bézout özdeşliği 1 = s × nᵢ + t × Nᵢ'ye ulaşır; böylece t tersidir. O zaman mod N'ye göre indirgenmiş x = a₁N₁y₁ + a₂N₂y₂ + … her denkleme uyar, çünkü her terim kendi denklemine uyar ve diğer hepsinde kaybolur.

Her seferinde bir denklem

Tüm modüllerin çarpımına ihtiyaç duymayan ikinci bir yol vardır. x ≡ 2 (mod 3) denkleminin her çözümü x = 2 + 3t biçimindedir. Bunu sonraki denklemde yerine koyun: 2 + 3t ≡ 3 (mod 5), yani 3t ≡ 1 (mod 5) ve 3'ün mod 5'e göre tersi olan 2 ile çarpınca t ≡ 2 (mod 5) elde edilir. O zaman x = 2 + 3 × 2 = 8 ve ilk iki denklem birlikte x ≡ 8 (mod 15) der. Üçüncü denklemle tekrarlayın: 8 + 15t ≡ 2 (mod 7) t ≡ 1 verir, yani x ≡ 23 (mod 105). Bu yerine koyma sayıları daha küçük tutar, bir bilgisayarın bu tür sistemleri genellikle çözme biçimidir ve modüllerin ortak çarpanı olduğunda da işe yarar.

Ortak çarpanlı modüller

İki modülün ortak çarpanı varsa denklemleri örtüşür: x ≡ 1 (mod 4) zaten x'in tek olduğunu söyler, x ≡ 4 (mod 6) ise x'in çift olduğunu; bu yüzden hiçbir x ikisini birden sağlamaz. Genel olarak x ≡ a (mod m) ve x ≡ b (mod n), tam olarak a ile b, g = gcd(m, n)'ye bölündüğünde aynı kalanı verdiğinde, yani g, a − b'yi böldüğünde aynı anda sağlanabilir. O zaman çözüm mod m × n'ye göre değil, mod lcm(m, n) = m × n / g'ye göre tektir. 2'şer, 3'er, 4'er, 5'er ya da 6'şar çıkarılınca 1, 7'şer çıkarılınca hiç artmayan yumurta sepeti bilmecesinin cevabı 301'dir ve her 420 = lcm(2, 3, 4, 5, 6, 7)'de bir tekrarlanır. Bir sistemin çözümü tam olarak her iki denklemi uyuştuğunda vardır; bu yüzden çözümsüz bir sistem her zaman çelişen bir çift içerir.

Takvimler, bilgisayarlar ve RSA

Joseph Scaliger 1583'te üç takvim döngüsünü, 28 yıllık güneş döngüsünü, 19 yıllık ay döngüsünü ve 15 yıllık indiksiyonu, 28 × 19 × 15 = 7.980 yıllık Jülyen döneminde birleştirdi. Teoreme göre her yılın üç döngü numarasından oluşan kendine özgü bir birleşimi vardır ve dönem, üçünün de 1 olduğu son yıl olan MÖ 4713'te başlar; gökbilimciler Jülyen günlerini hâlâ oradan sayar. Bilgisayarlar teoremi, dev sayılarla küçük kalanların listeleri olarak hesap yapmak için kullanır; bu kalanlar ayrı ayrı ve paralel olarak toplanıp çarpılabilir, sonunda birleştirilir. RSA şifre çözme de aynı şekilde çalışır: n = p × q iken c^d mod n, teoremle birleştirilen iki kuvvet olarak, mod p ve mod q'da hesaplanır; bu, tek bir mod n kuvvetinden yaklaşık dört kat hızlıdır. Mignotte'un ve Asmuth ile Bloom'un şemaları gibi sır paylaşım şemaları, bir sırrı kalanlara gizler; böylece ancak yeterince kalan bir araya gelince sır ortaya çıkar.

Ron Rivest, Adi Shamir ve Len Adleman (soldan sağa)
Ron Rivest, Adi Shamir ve Len Adleman (soldan sağa)

Kendiniz deneyin

En fazla 20 denklem ve en fazla 200 basamaklı sayılarla herhangi bir denklik sistemi yazmak için çözücüyü açın ya da çözümlü örneklerden birini seçin: Sunzi'nin problemi, yumurta sepeti, Jülyen dönemi, iki otobüs sefer çizelgesi, RSA şifre çözme ve çözümü olmayan bir sistem. Çözüm yolu sizin sayılarınızla, kurulumla ya da yerine koyma yöntemiyle, her ters için genişletilmiş Öklid algoritmasıyla yazılır. Görsel her denklemi sağlayan sayıları işaretler; böylece hepsinin buluştuğu tek sütunu görürsünüz. Ya da iki denklemin kalanlarını, her sayının kendi hücresi olduğu bir tabloya yerleştirir.

Sık sorulan sorular

Bir denklik sisteminin çözümü tek midir?

Yalnızca modülün bir katına kadar. x = 23 Sunzi'nin problemini çözüyorsa 23 + 105 = 128, 233 ve −82 de çözer, çünkü 105 eklemek kalanların hiçbirini değiştirmez. Teorem, 0 ile 104 arasında tam olarak bir çözüm olduğunu söyler; ortak çarpanlı modüllerde ise en küçük ortak katlarının altında tam olarak bir çözüm.

Modüller neden aralarında asal olmalı?

Kurulum için, çünkü Nᵢ'nin mod nᵢ'ye göre bir tersi olmalıdır ve bu ancak ortak çarpanları yoksa vardır. Teoremin kendisi için, çünkü ortak çarpanlar bazı denklemleri örtüştürür: o zaman bir sistemin ya hiç çözümü olmaz ya da daha az farklı çözümü olur ve çözümler her çarpımda değil, her en küçük ortak katta bir tekrarlanır.

Modüler tersi elle nasıl bulurum?

Genişletilmiş Öklid algoritmasıyla. 15'in mod 7'ye göre tersi için: 15 = 2 × 7 + 1, yani 1 = 15 − 2 × 7 ve 15 × 1 ≡ 1 (mod 7): ters 1'dir. 35 mod 3 için: 35 = 11 × 3 + 2 ve 3 = 1 × 2 + 1, yani 1 = 3 − 2 = 3 − (35 − 11 × 3) = 12 × 3 − 35 ve 35'in mod 3'e göre tersi −1 ≡ 2'dir. Küçük modüllerde çarpım 1 kalanını verene kadar 1, 2, 3, … denemek de olur.

Teoremin saatlerle ne ilgisi var?

Mod n'ye göre bir kalan, n saatlik bir saatte bir konumdur. Birlikte başlatılıp birer saat ilerletilen 3 ve 5 saatlik iki saat, başa dönmeden önce 15 konum çiftinin her birini bir kez gösterir, çünkü 3 ile 5'in ortak çarpanı yoktur. 4 ve 6 saatlik saatler 12 adımda başa döner ve 24 çiftin yalnızca 12'sini gösterir: tek ve çift bir konum asla birlikte görünmez.

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

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

Çin kalan teoremi çözücüsünü açın