• misal:

    a=x (mod k)
    a=y (mod m)
    a=z (mod n)

    eşitlik sisteminde x,y,z,k,m,n verildiğinde a'yı bulmaya yarayan, uygulama alanı geniş teorem.
  • cinlilerin bu teoremi ispatladigi donemde zamanin hukumdari turk bilim adamlarina bu teoremin turk versiyonunu ispatlamalarini emretmis. turk bilim adamlari da turk bolen teoremini ispatlamislar.
  • yemeyip te yaninda yatilacak bir number theory konseptidir.
    z = { 0, 1, -1, 2, -2, ... }
    az = { an | n in z }
    z_a = z/az diye tanimlarsak, ki bu bir field olur, ve { 0, 1, .. , a-1 } grubuna modulo toplama/carpma ile izomorfiktir;

    crt buyurur ki; eger gcd(a,b)=1 ise, o vakit z_a * z_b ~= z_{ab} (izomorfizm)

    ornekle gormek cok daha kolay olacak..

    a=2, b=3
    z_a = { 0,1 }, z_b = { 0,1,2 }, z_ab = {0,1,2,3,4,5}

    $imdi crt diyor ki eger $oyle bir f tanimlarsaniz;
    f(0)=(0,0)
    f(1)=(1,1)
    f(2)=(0,2)
    f(3)=(1,0)
    f(4)=(0,1)
    f(5)=(1,2)

    $imdi her x, y icin f(xy)=f(x)f(y) olur.. ozellikle bilgisayarda asal olmayan sayilarda modulo cali$irken inanilmaz yardimci olur, akillara durgunluk verir
  • daha basit bir ornek ile:

    ali'nin elinde 11 cm'lik bir cetvel olsun. ali uzunlugu "x" olan kumas parcasini olcmek icin inatla bu kisa cetveli kullanmaktadir. ali'nin kotu bir ozelligi de inatciligina ek olarak dalgin olmasidir. ali kumasin uzunlugunu olcerken cetvele defalarca taklalar attirarak kumasin sonuna ulasmis ve kumasin son takladan sonra 3 cm daha uzun oldugunu musaade etmistir. ali dalgin oldugundan cetvele kac takla attirdigini unutmustur*.

    bu durumda kumas eger sifir takla yapildiysa 3cm, bir takla yapildiysa 14 cm, iki takla yapildiysa 25 cm olabilir. olasilik kumesini siralarsak = { 3, 3+11, 3+2x11, 3+3x11 , 3+4x11 , .... }

    ayse ayni manifaturacida calisan akli bir karis havada bir kizcagizdir*. aysenin elindeki cetvel 15 cm'lik bir seydir. ayse ayni olcumu yapinca 15 cm'lik cetvel taklalari sonunda kalan kumas parcasi 5 cm cikmistir. ayse'nin olcumden cikan olasiliklar ise sunlardir ={ 5, 5+15, 5+2x15, 5 + 3x15, 5+4x15, ... }

    patronlari odtu matematik bolumu mezunu olan muttalip beyefendi bu iki calisani cok sevip aralarini yapmak istediginden isyerinde herhangi bir huzursuzluk ciksin istememektedir. olcum problemi sorunsuzca halletmek icin muttalip beye yardimci olunuz.

    cevap:
    iki kumenin kesisimi alirsaniz iki kosulu da saglayan sayilar kumesini elde etmis olursunuz. isterseniz once bu kumeyi bir ifade edelim, sonra tartismamiza devam ederiz:

    ali'nin olcumleri kesisim ayse'nin olcumleri = { 80 , 80 + 15x11 , 80 + 2x15x11 , 80 + 3x15x11 }

    ilk cozum olan 80 sayisi, 11'e bolunce 3 kalanini veriyor (80 = 77 +3); 15'e bolunce 5 kalanini (80 = 75 + 5). dalgin tezgahtarlarin olcumleriyle uyumlu olan en kucuk sayi 80'dir. bir sonraki sayi ise 80 + 15x11 = 245'dir.

    eger kumasin 245 cm'den kisa oldugunu tahmin ediyorsaniz (goz var izan var) olasi tek cevap 80'dir.

    simdi gelelim muttalip amcaya yardimci olmak icin bizden beklenen aciklamaya:
    x = [ m1*15* [ 15^{-1} mod 11 ] + m2*11*[ 11^{-1} mod 15] ] mod 15*11
    bizim aradigimiz cozum denklemidir. burada m1 11cm'lik cetvel olcum sonucundan arta kalan miktari; m2 de 15cm'lik olcum sonucundan arta kalan miktari temsil eder.

    15^{-1} mod 11 ise 15'in modulo 11'deki carpmaya gore olan tersidir. yani efenim 15x3=45 oldugundan 45 de modulo 11'de 1 oldugundan bu rakam 3'tur.

    ayni sekilde 11^{-1} mod 15 ise 11'dir.

    toparlarsak

    x = m1*45 + m2*121 mod 165 aradigimiz ifadedir.

    ali ve ayse'den m1 ve m2 degerlerini alan muttalip bey yukaridaki formulu kullanarak kumasin uzunlugunu hesaplayabilir. goruyorsunuz son denklemde ne kume ne de kesisim operasyonu vardir, cozumu hasirt diye buluyoruz. bravo cinlilere.

    not:
    teoremin** ispati da gayet basittir. ispat aralarinda asal olan iki sayi icin verilip kolaylikla genellenebilir. aralarinda asal olma kosulunu dikkatlice kullanmak ispat icin yeterlidir. yukaridaki ornegi dikkatle takip edenler tam bir ispati kolaylikla deduce edebilirler**.
  • rsa tarafından anahtar üretimi ve decryption için kullanılır.
  • rsa tarafından kullanılması halinde sistemi side channel attack'lara maruz bırakabilen yöntem.
  • bir sayı 3'e bölündüğünde 2, 5'e bölündüğünde 3, 7'ye bölündüğünde de 2 kalıyor. sayı kaçtır?

    x=2 (mod3)
    x=3 (mod5)
    x=2 (mod7)

    x=23, genel formül de 23+105k

    yerine koyma metodu veya çin kalan teoremi ile çözülür. kısaca 2'ye denk olan modların çarpılıp 2 eklenmesi ve artış miktarının hesabı için de modların hepsinin çarpılması yeterlidir.
    zamanında çinli arkadaşlar orduyu saymak için geliştirmiş bunu.

    örnekleyerek gösterdim, matematikten anlayan arkadaşlar varsa uzun uzadıya anlatabilirler.

    yeni örnekler ile geldim olay iyice açıklığa kavuşsun diye. basit şeylerden başlayacağım.
    -----
    x=0 (mod2)
    x=0 (mod3)
    x=0 (mod5)

    bunu sağlayan en ufak sayımız 2, 3 ve 5 aralarında asal olduğu için 30. genel formülü ise 30k.
    -----
    x=0 (mod2)
    x=0 (mod5)
    x=0 (mod8)

    bunu sağlayan en ufak sayımızı ise aralarında asallık söz konusu olmadığı için asal çarpanlardan yapacağız
    2-5-8|2
    1-5-4|2
    1-5-2|2
    1-5-1|5
    1-1-1|
    ki bu da 2^3 ve 5. en ufak sayı 40 geliyor burada yani aralarında asal olan sayılarda yaptığımız gibi hepsini birbiriyle çarpmadık aslında. bunun da genel formülü 40k oldu.
    -----
    şimdi işleri karıştıralım biraz.

    x=2 (mod3)
    x=2 (mod5)
    x=2 (mod7)

    kalanlar 0'dan büyük ve aynıyken yapmamız gereken şey yine aralarında asallığa bakmak, ardından kalanımızı buna eklemek. yani genel formülü 2(kalan aynı çünkü) + 105k.
    -----
    peki aralarında asallık yok ise?

    x=1 (mod2)
    x=1 (mod3)
    x=1 (mod4)

    2 ile 4 asallığı bozuyor ne yazık ki. asal çarpanlara ayırınca ise elimize 2^2 ve 3 geliyor. bu durumda kalan yine aynı olduğu için kalan + katlar şeklinde düzenliyoruz genel formülü. ki bu da 1+12k oluyor.
    -----
    hiçbirinin aralarında asallığı yoksa peki?

    x=1 (mod2)
    x=3 (mod4)
    x=5 (mod6)

    görüldüğü üzere hepsinin içinde 2 var.
    2-4-6|2
    1-2-3|2
    1-1-3|3
    1-1-1|

    2^2 ve 3 bölenlerimiz. en ufak değerimiz 11 ve formülümüz de 11+12k.
    -----
    e basitten alıyorsun sen de diyeceksiniz bu noktada. haklısınız. bakalım kalanlar farklı olunca neler dönüyor.

    x=1 (mod2)
    x=2 (mod3)
    x=5 (mod7)

    aha şimdi sıçtık. bütün kalanlar birbirinden farklı ve sayılar da aralarında asal. sıkıntı yok. sakin kafayla yapmaya çalışıyoruz.
    önce mod2 ve mod3 bakalım. bunu sağlayan en ufak değer 5. ardından bunu birleşik kabul edip mod7nin kuralı ile karşılaştırıyoruz. 5 mod7'de de hala 5. demek ki en ufak değerimiz 5. aralarında asallık olduğu için hepsini çarpıyoruz ve genel formülü 5+42k çıkıyor. inanılmaz gelebilir evet ama 5den sonraki en yakın değer 47dir ve 2 için 46+1, 3 için 45+2, 7 için 42+5 şeklinde gelir.
    -----
    peki kalanlar arasında karmaşıklık olursa ne olacak? gruplaştırarak çözdüğümüzde diğer bir moda uymayabilir bulduğumuz değer. hemen onu da yapalım.

    x=1 (mod2)
    x=2 (mod5)
    x=3 (mod7)

    aslında aradığımız hali ise şu:
    x=7 (mod10)
    x=3 (mod7)

    en küçük değer 17 ve kural da 17+70k. işler gittikçe karışıyor gibi değil mi?
    -----
    aralarında asallığı bozarsak neler olur acaba diye bakalım kafaları temizlemek için.

    x=2 (mod3)
    x=1 (mod5)
    x=3 (mod6)

    bu sefer bittik işte. ne yazık ki böyle bir tam sayı henüz yok.
    -----
    son kez de şunu deneyelim:
    x=1 (mod2)
    x=3 (mod7)
    x=4 (mod8)

    ne yazık ki bu da yok.
    -----
    son 2 örneğin olmama sebebi ise aralarında asal olmayan modlarımızın büyük mod için artan sayısının küçük mod'a bölünebiliyor olması.
    ilk örnek için mod6'nın kalanı olan 3'ün mod3'e bölünebilmesi, ikinci örnek için ise mod8'in kalanı olan 4'ün mod2'ye bölünebilmesi. bağımsız şeyler seçildiği her durumda sağlayacaktır kendini.

    not: niye hepsini 3 modlu yapıyorsun derseniz, en küçük tek asal sayı olduğu için işimi zorlaştırıyor aslında. 2 tane mod arasında yaparsam gayet basit olurdu. 4 tane yaparsam da 2-2 gruplandırıp yapabilirdim. en iyisinin bu olduğuna karar verdim.
hesabın var mı? giriş yap