Chinese Remainder Theorem

Merhaba,
Bu yazımda, elimden geldiğinde Discrete Structures dersinde görmüş olduğum Chinese Remainder Theorem’i anlatmaya çalışacağım. Bu teorem ilk olarak Çinli matematikçi Sun Tzu tarafından tam olarak bilinmemekle birlikte 4. yüzyıl civarında kullanılmış. Eski bir hikayeye göre, Çin hükümdarı bu teoremi ordudaki asker sayısını hesaplamak için kullanırmış. Peki nasıl? Hükümdar, askerlerinden önce 3’erli sonra 5’erli ve son olarak 7’şerli gruplara bölünmesini istemiş. Her gruplaşmadan sonra grup dışında kalan askerlerin sayısını öğrenirmiş. Sonunda, imparator kaç tane asker olduğunu hesaplarmış.

Diyelim ki, ordumuzda N tane asker var. N asker 3’erli grup olduklarında 1, 5’erli ve 7’şerli grup olduklarında 2 asker dışarıda kalıyor. Bu da demek oluyor ki;

N ≡ 1 (mod 3)
N ≡ 2 (mod 5)
N ≡ 2 (mod 7)

1. denklem için (N ≡ 1 (mod 3)); N ∈ {1, 4, 7, 10, 13, … , 34, 37, 40, 43, 46, …, 139, 142, 145, …}
2. denklem için (N ≡ 2 (mod 5)); N ∈ {2, 7, 12, 17, 22, … , 32, 37, 42, 47, 52, …, 137, 142, 147, …}
3. denklem için (N ≡ 2 (mod 7)); N ∈ {2, 9, 16, 23, 30, 37, 44, 51, 58, …, 135, 142, 149, …}

Yukarıdan da görüldüğü gibi, N sayısının koşulu ilk olarak 37 sayısında, daha sonra 37+105(3*5*7)=142 sayısında sağlanıyor. Peki, bir sonraki N sayısı nedir? 142+105= 247

Kullanmış olduğumuz bu yöntemle istenen sayıyı bulmak bir hayli zaman alır. Bu sayıyı bulmak için, işimizi kolaylaştıran bir formülümüz olacak;
N ≡ [(n1*b1*c1)+(n2*b2*c2)+(n3*b3*c3)] (mod 105)

Şimdi, formüldeki bilinmeyenleri bulalım.

“c” dediğimiz değişken, kalanlar; yani c1=1, c2=2, c3=2

“b” bilinmeyenini bulmak için ise şöyle bir yol izleyeceğiz. B=105 dersek (3*5*7);
b1=B/(3), yani b1=105/3=35. Bir başka söylemle, b1=5*7=35
b2=3*7=21
b3=3*5=15

“n” bilinmeyenlerimizi ise aşağıdaki adımları takip ederek hesaplayacağız:
(n1*b1) ≡ 1 (mod c1)
(n1*35) ≡ 1 (mod 3)
(n1*2) ≡ 1 (mod 3)
(n1*2) ≡ (1+3) (mod 3)
(n1*2) ≡ 4 (mod 3)
n1=2

(n2*b2) ≡ 1 (mod c2)
(n2*21) ≡ 1 (mod 5)
(n2*1) ≡ 1 (mod 5)
n2=1

(n3*b3) ≡ 1 (mod c3)
(n3*15) ≡ 1 (mod 7)
(n3*1) ≡ 1 (mod 7)
n3=1

Bu sonuçlarla, formülümüzdeki bütün değişkenleri bulmuş olduk. Yerlerine koyarsak eğer:
N ≡ [(2*35*1)+(1*21*2)+(1*15*2)] (mod 105)
N ≡ 142 (mod 105)
N ≡ 37 (mod 105)
N=37

Chinese Remainder Theorem” üzerine 4 düşünce

  1. gndzyarenn

    Merhabalar, Çin kalan teoremi ile ilgili yazınızı okudum, bende birkaç haftadır üzerinde çalıştım ama neredeyse her siteyi gezmeme rağmen bu teoreminin nasıl yapıldığı hakkında milyonlarca kaynak bulurken, neden gerek duyulduğu ile ilgili en ufak detay bile bulamadım ve üzerinde gerçekten çok düşündüm. Sizin bu konu hakkındaki bir bilginiz veya küçük bir detay bilmeniz bile bana çok yardımcı olur, çünkü bu bilgiye gerçekten çok ihtiyacım var.Şimdiden teşekkür ederim.

    Beğen

    Cevapla
    1. symphsodon Yazıyı Yazan

      Merhabalar,
      Yazacağım bilgilerin kesinliğini referans eden resmi/akademik bir kaynak bilmiyorum ancak daha önceden okuduklarımdan aklımda kalanlar şöyle:
      Öncelikle bu teorem Çinli komutan Sun Tzu’ya ait ve Sun Tzu MÖ 500 yıllarında yaşamış birisi.
      Dediğim gibi, bu adam asker ve o zamanki Çin ordusunun büyüklüğünü hesaplamak istemişler. Bunun üzerine kafa yorarlarken Sun Tzu ortaya bu teoremi sunmuş ve kabul görmüş. Bu da nasıl oluyor? Şöyle, askerler önce üçerli, sonra beşerli, sonra da yedişerli gruplara ayrılmışlar ve her grup için “artık kalan” asker sayısı belirlenmiş. Elde edilen bu verileri, teoreme uygun olacak şekilde kullanarak, o zamanki orduda bulunan asker sayısını hesaplamışlar.

      Örnek vermek gerekirse:
      Üçerli gruplara ayrıldıklarında 2 asker,
      Beşerli gruplara ayrıldıklarında 4 asker,
      Yedişerli gruplara ayrıldıklarında 6 asker,
      artmış ve teoremi kullanarak ordudaki toplam asker sayısının 1049 olduğunu öngörmüşler.

      Harvard’da yayınlanmış bir makaleye göre, bu teorem yine antik Çin’de takvim oluşturmak için kullanılmış. Şuradan göz atabilirsiniz: http://www.math.harvard.edu/~knill/crt/lib/Kangsheng.pdf

      Not: Yazıda da aynı hikayeyi anlatmışım aslında, yazıya göz gezdirmeden yanıt yazmış bulundum. Bildiğim kadarıyla teoremin çıkış noktası budur.

      Beğen

      Cevapla
      1. gndzyarenn

        İlginiz için teşekkür ederim,yazdıklarınızı dikkate alacağım.Sadece ne oluyorda böyle bir teoremde modlar gruplamalar veya gcdler ve moduler terslerle ilişkileniyor bunu anlamak için sormuştum, kafamdada birkaç birşeyler canlandı.Tekrardan teşekkür ederim.

        Beğen

Bir Cevap Yazın

Aşağıya bilgilerinizi girin veya oturum açmak için bir simgeye tıklayın:

WordPress.com Logosu

WordPress.com hesabınızı kullanarak yorum yapıyorsunuz. Çıkış  Yap /  Değiştir )

Google fotoğrafı

Google hesabınızı kullanarak yorum yapıyorsunuz. Çıkış  Yap /  Değiştir )

Twitter resmi

Twitter hesabınızı kullanarak yorum yapıyorsunuz. Çıkış  Yap /  Değiştir )

Facebook fotoğrafı

Facebook hesabınızı kullanarak yorum yapıyorsunuz. Çıkış  Yap /  Değiştir )

Connecting to %s

This site uses Akismet to reduce spam. Learn how your comment data is processed.