Çin Kalan Teoremi (Chinese Remaining Theorem)

Question

Çin matematikçisi Sun Zi şu soruyu sorar:Bir sayı 3'e bölündüğünde 2 kalıyor, 5'e bölündüğünde 3 kalıyor , 7'ye bölündüğünde de 2 kalıyor.Sayı kaçtır?

 Modern matematik dilinde bu soru, 

$x\equiv 2mod3$

$x\equiv 3mod5$

$x\equiv 2mod7$

denkliklerini çözmeye eşdeğerlidir. Bu yazıda bu tür denkliklerin ne zaman bir çözümü olduğunu ve çözümü olduğunda çözümün nasıl bulunduğunu göreceğiz.

Answer 1

Birinci denklikten, $t\in Z$ için,

                           $x=3t+2$

buluruz.Bunu ikinci denkliğe yerleştirirsek,

                          $3t+2\equiv 3mod5$

yani

                         $3t\equiv 1mod5$

buluruz.Her iki tarafı da 2 yle çarparsak (2, 3 ün modülo 5 tersidir; $2.3\equiv 1mod5$,

                         $t\equiv  2mod5$

buluruz.Demek ki,belli bir $s\in Z$ için 

                         $t=5s+2$

Bunu yukarıdaki $x=3t+2$ eşitliğine yerleştirirsek,

                        $x=15s+8$

buluruz.Bunu da üçüncü denkleme yerleştirelim:

                       $15s+8\equiv 2mod7$,

yani

                      $s\equiv 15s\equiv -6\equiv 1mod7$

buluruz.Demek ki, belii bir $u\in Z$ için

                      $s\equiv 7u+1$.

Bunu $x=15s+8$ e yerleştirirsek,

                     $x\equiv 105u+23$

bulunur.En küçük pozitif çözüm $u=0$ içindir, yani 23 tür.Denklikleri teker teker çözme ilkesine dayanan,ilkel ve oldukça karmaşık bir çözüm...

Comments

Teşekkür ederim.