Chinese Remainder Theorem


Diberikan sistem kongruensi sebagai berikut.




haruslah saling relatif prima
Dengan demikian, kita dapat mencari nilai  dengan rumus berikut.

dimana

untuk setiap .
dan  adalah invers dari  modulo  untuk setiap .

———————————————————————————————————-

contoh:

Suatu bilangan bulat positif akan bersisa 1 jika dibagi 3, bersisa 2 jika dibagi 5, dan bersisa 3 jika dibagi 7. Tentukan bilangan bulat terkecil yang memenuhi kondisi tersebut.

Karena 3,5, dan 7 relatif prima, maka rumus CRT (Chinese Remainder Theorem) dapat langsung digunakan.
Kita dapatkan , dan . Untuk menentukan , kita selesaikan , menjadi , maka . Untuk menentukan , kita selesaikan , maka . Untuk menentukan , kita selesaikan , maka 
Tinggal memasukkan semua elemen yang ada ke dalam rumus

Jadi, bilangan yang dimaksud adalah 52.
sederhana bukan?

About ardiantoarsadi

don't look for miracles it will come

Posted on Desember 18, 2009, in MATERI MATEMATIKA. Bookmark the permalink. Tinggalkan komentar.

Tinggalkan Balasan

Isikan data di bawah atau klik salah satu ikon untuk log in:

Logo WordPress.com

You are commenting using your WordPress.com account. Logout / Ubah )

Gambar Twitter

You are commenting using your Twitter account. Logout / Ubah )

Foto Facebook

You are commenting using your Facebook account. Logout / Ubah )

Foto Google+

You are commenting using your Google+ account. Logout / Ubah )

Connecting to %s

%d blogger menyukai ini: