Makalah "Teorema Sisa Cina - Matematika"

TEORI BILANGAN

”CHINESE REMAINDER THEOREM”

M A K A L A H

 Disusun oleh :

v  M. Farhan Muzaky                 063141111005

v  Muplih                                 063141111007

v  Asep M. Misbahudin              063141111019

Pendidikan Matematika

Universitas Muhammadiyah Sukabumi (UMMI), Sukabumi

2012

KATA PENGANTAR

Puji dan syukur penyusun panjatkan ke hadirat ALLAH SWT., karena dengan rahmat-Nya kami dapat menyelesaikan pembuatan Makalah ini.

Maksud dan tujuan dari pembuatan Makalah ini adalah untuk memenuhi salah satu tugas Mata Kuliah “Teori Bilangan”.

Dengan segala kerendahan hati, kami menyampaikan terima kasih kepada para pihak yang terkait dalam pembuatan Makalah ini, diantaranya kepada :

1.                  Ibu Rahmi Latifah, selaku dosen Mata Kuliah “Teori Bilangan”.

2.                  Kedua Orangtua penyusun, yang selalu memberikan do’a dan motifasinya kepada penyusun.

3.                  Teman-teman dan kepada pihak lain yang telah memeberikan bantuannya dalam pembuatan Makalah ini.

            Penyusun menyadari bahwa Makalah ini masih jauh dari sempurna, oleh karena itu penyusun mengharapkan saran dan kritik dari semua pihak yang bersifat membangun untuk perbaikan di masa yang akan datang. 

            Semoga Makalah ini dapat bermanfaat bagi semua pihak yang membutuhkannya.

Sukabumi, 28 Juni 2012

Penyusun

DAFTAR ISI

Kata Pengantar                                                                                                           i

Daftar Isi                                                                                                                     ii

Bab I                                                                                                                          1

Pendahuluan                                                                                                                1

1.1.            Umum                                                                                                                         1

Bab II                                                                                                                          3

Pembahasan                                                                                                                 3

2.1.      Teorema Sisa Cina (Chinese Remainder Theorem)                                            3

2.1.1.   Teorema Sisa Cina                                                                                3

2.1.2.   Penggunaan Teorema Sisa Cina                                                             4

Bab III                                                                                                                          12

Penutup                                                                                                                         12

3.1.Kesimpulan                                                                                                              12

BAB  I

PENDAHULUAN

1.1.            Umum

Konsep perhitungan matematika telah berkembang sejak jaman Mesir kuno, Mesopotamia, dan Yunani. Menurut Prof. Marcus Du Sautoy Tembok Besar Cina adalah prestasi luar biasa dari teknik pembangunan. Setelah mereka mulai membangun, orang Cina mulai menyadari bahwa mereka harus membuat perhitungan tentang jarak, sudut elevansi, dan jumlah material. Ketika seorang matematikawan ingin meghitung penjumlahan maka mereka menggunakan batang bambu kecil. Batang itu disusun untuk mewakili angka satu sampai sembilan, kemudian angka-angka tersebut di tempatkan dalam kolom dimana setiap kolom mewakili satuan, puluhan, ratusan dan ribuan. Misalnya 924 diwakili dengan meletakkan 4 pada satuan, 2 pada puluhan, 9 pada ratusan. Inilah yang disebut sistem nilai desimal. Namun Cina belum memiliki simbol untuk nol. Saat menggunakan batang untuk menghitung, mereka menggunakan ruang kosong untuk membangkan angka nol. Mereka memiliki kepercayaan bahwa angka memiliki kekuatan mistis. Angka ganjil dianggap sebagai laki-laki dan angka genap dianggap sebagai perempuan. Dan angka delapan dianggap sebagai angka keberuntungan.

Pada tahun 1809, ketika menganalisis batu yang disebut Pallas, Carl Friedrich Gauss menemukan kembali metode Cina yang telah ada sejak dulu yang dikenal dengan teorema sisa Cina. Contohnya, seorang wanita di pasar memiliki nampan telur, tapi ia tidak tau berapa jumlah telur yang dimiliki. Bila telur disusun dalam deret tiga, maka akan sisa satu. Bila disusun dalam deret lima maka akan sisa dua. Dan bila disusun dalam deret tujuh akan sisa tiga. Kemudian orang Cina dapat menemukan cara sistematis untuk menghitung bahwa jumlah telur dalam nampan sebanyak 52.

Pada abad ke-6, Teorema Sisa Cina telah digunakan dalam astronomi Cina kuno untuk mengukur pergerakan planet. Matematikawan yang terkenal adalah Qin Juishao. Beliau adalah seorang administator kekaisaran yang berulang kali dipecat karena menggelapkan uang pemerintahan. Namun beliau memiliki prestasi, yaitu beliau menemukan cara untuk memecahkan persamaan kubik. Dan pada abad ke-17 Isaac Newton datang dengan metode pendekatan yang sangat mirip.

  

BAB II

PEMBAHASAN

2.1.      Teorema Sisa Cina (Chinese Remainder Theorem)

2.1.1.   Teorema Sisa Cina

Bentuk asli dari teorema ini, seperti terdapat dalam buku yang ditulis oleh ahli matematika dari Cina Qin Jiushao dan diterbitkan pada tahun 1247, adalah suatu pernyataan tentang kongruensi simultan (lihat aritmatika modular).

Misalkan n₁, ..., n_k adalah bilangan bulat positif yang setiap pasangnya adalah koprima (yang artinya FPB (n_i, n_j) = 1 untuk setiap i ≠ j). Maka, untuk setiap bilangan bulat a₁, ..., a_k, selalu ada bilangan bulat x yang merupakan penyelesaian dari sistem kongruensi simultan

Dalam pemrograman pada sebuah computer (misal, pada Borland C), dapat kita lihat Pseudocode "subtitle" seperti berikut :

x_solves_it=true;

for (i= 1; i <= k; i++)

      if (x % n[i] != a[i] % n[i])

          x_solves_it=false;

Terlebih lagi, semua penyelesaian x dari sistem ini adalah juga kongruen modulo dari perkalian n = n₁...n_k.

Suatu penyelesaian x dapat ditemukan dengan cara sebagai berikut. Untuk setiap i, bilangan bulat n_i dan n/n_i adalah koprima, dan menggunakan ekstensi algoritma Euklidean kita dapat menemukan bilangan bulat r dan s sehingga r n_i + s n/n_i = 1. Jika kita menentukan e_i = s n/n_i, maka kita dapat :

untuk j ≠ I :      for (i= 1; i <= k; i++)

                   {r, s}= ExtendedEuclid( n[i], n / n[i] );

                   e[i]= s * n / n[i];

                   for (j= 1; j <= k; j++)

                   if (j != i)

                       assert( e[i] % n[i] == 1 && e[i] % n[j] == 0 );

Penyelesaian dari sistem kongruensi simultan ini adalah

For (i= 1; i <= k; i++)

       x += a[i] * e[i];

Sebagai contoh, misalkan kita ingin menemukan suatu bilangan bulat x sehingga,

 x % 3 == 2 % 3 && x % 4 == 3 % 4 && x % 5 == 2 % 5

Menggunakan ekstensi algoritma Euklidean untuk 3 dan 4×5 = 20, kita memperoleh (-13) × 3 + 2 × 20 = 1, di mana e₁ = 40 (e[1] == 40). Menggunakan algoritma Euklidean untuk 4 dan 3×5 = 15, kita memperoleh (-11) × 4 + 3 × 15 = 1. Oleh karena itu, e₂ = 45 (e[2] == 45). Akhirnya, menggunakan algoritma Euklidean untukr 5 dan 3×4 = 12, kita memperoleh 5 × 5 + (-2) × 12 = 1, yang berarti e₃ = -24 (e[3] == -24). Jadi, penyelesaian x adalah 2 × 40 + 3 × 45 + 2 × (-24) = 167. Semua penyelesaian yang lain adalah kongruen 167 modulo 60, yang berarti bahwa mereka semua kongruen 47 modulo 60.

Kadangkala, sistem kongruensi simultan dapat diselesaikan sekalipun n_i (n[i]) setiap pasangnya tidak selalu koprima. Syarat-syarat yang lebih tepat adalah sebagai berikut : sistem mempunyai penyelesaian x jika dan hanya jika a_i ≡ a_j (mod fpb(n_i, n_j)) (a[i] == a[j] % gcd(n[i], n[j])) untuk semua i dan j. Semua penyelesaian x adalah kongruen modulo kelipatan persekutuan terkecil dari n_i (n[i]).

Dengan menggunakan metode substitusi, kita seringkali bisa menemukan penyelesaian dari sistem kongruensi simultan, sekalipun setiap pasang modulusnya tidak selalu koprima.

2.1.2.   Penggunaan Teorema Sisa Cina

Tercatat dalam literatur Cina, pada abad pertama Sun-Tsu mengajukan sebuah permasalahan seperti berikut, “Tentukan bilangan yang memberikan sisa 2, 3, 2 ketika dibagi oleh 3, 5, dan 7!!”. Untuk menyelesaikan permasalahan tersebut dapat diselesaikan dengan menggunakan Teorema Sisa Cina.

Teorema Sisa Cina :

Misalkan n1, n2, n3, ... , nr bilangan bulat positif sedemikian sehingga FPB (ni, nj) = 1, untuk i.j.

Sistem Kongruensi Linier x =a1 (mod n1)

x =a2 (mod n2)

x =a3 (mod n3)

.

.

.

x =ar (mod nr)

memiliki solusi yang unik dengan modulo n1 x n2 x n3 x ... x nr.

Contoh 1 :

Permasalahan yang diberikan oleh Sun-Tsu berkorespondensi dengan tiga sistem kongruen

Berikut :

x =2 (mod 3)

x =3 (mod 5)

x =2 (mod 7)

untuk menyelesaikan permasalahan di atas, digunakan Teorema Sisa Cina.

Penyelesaian :

Cara I :

·         Langkah I : Identifikasi unsur yang diketahui.

a1= 2, a2 = 3, dan a3 = 2

n1 = 3, n2 = 5, dan n3= 7

·         Langkah II : Cari nilai n dengan rumus n = n1 x n2 x n3 x ... x nr

Jadi, n = n1 x n2 x n3 = 3 x 5 x 7 = 105.

·         Langkah III : Cari nilai Nk untuk k = 1, 2, 3 dengan rumus Nk = .

N1 = 35, N2 = 21, N3 = 15.

·         Langkah IV : Cari nilai xk, dari kongruensi linier Nkxk = 1 (mod nk), dengan k = 1, 2, 3.

Jadi,

N1x1 = 1 (mod n1). 35x1 = 1 (mod 3). x1 = 2

N2x2 = 1 (mod n2). 21x2 = 1 (mod 5). x2 = 1

N3x3 = 1 (mod n3). 35x3 = 1 (mod 3). x3 = 1

·         Langkah V : Tentukan solusi dari sistem yang diberikan dengan rumus,

= a1N1xk + a2N2x2 + ... + arNrxr modulo n, untuk k = 1, 2, ... , r

Sehingga diperoleh solusi :

= a1N1xk + a2N2x2 + a3N3x3

= 2 x 35 x 2 + 3 X 21 X 1 + 2 X 15 X 1

= 233.

modulo 105

Jadi, solusi unik dari sistem kongruensi yang diberikan : x = 233 =23 (mod 105).

Cara II :

Untuk menyelesaikan permasalahan Sun-Tsu dapat diselesaikan dengan teorema sisa cina, dengan langkah berikut.

·         Langkah I :

Tuliskan unsur yang diketahui.

x =2 (mod 3)

x =3 (mod 5)

x =2 (mod 7)

·         Langkah II :

Pilih salah satu persamaan kongruensi, misalkan x = 2 (mod 3) kemudian rubah dalam definisi. Catatan, pilih persamaan kongruensi yang bentuknya paling sederhana. Hal ini untuk mempermudah pengerjaan. Sehingga diperoleh, x = 2 (mod 3) .x = 2 + 3p, dengan p .Z.

·         Langkah III :

Substitusikan x = 2 + 3p ke persamaan kongruensi kedua yakni x = 3 (mod 5).

Sehingga diperoleh,

2 + 3p = 3 (mod 5)

3p = 1 (mod 5)

3p = 1 (mod 5), dan

2 = 2 (mod 5)

6p = 2 (mod 5)

p = 2 (mod 5)

Berdasarkan definisi,

p = 2 (mod 5)

p = 2 + 5q, dengan q .Z.

·         Langkah IV :

Substitusikan p = 2 + 5q ke persamaan x = 2 + 3p.

Sehingga diperoleh, x = 2 + 3p = 2 + 3(2 + 5q) = 2 + 6 + 15q = 8 + 15q.

·         Langkah V :

Substitusikan x = 8 + 15q ke persamaan kongruensi ketiga yakni x = 2 (mod 7).

Sehingga diperoleh,

8 + 15q =2 (mod 7)

q =1 (mod 7)

Berdasarkan definisi,

q = 1 (mod 7)

q = 1 + 7r, dengan r .Z.

·         Langkah VI :

Substitusikan q = 1 + 7r ke persamaan x = 8 + 15q.

Sehingga diperoleh, x = 8 + 15q = 8 + 15(1 + 7r) = 23 + 105r. x = 23 (mod 105).

Jadi, solusi unik dari sistem kongruensi yang diberikan adalah x = 233 = 23 (mod 105).

Contoh 2 :

Tentukan penyelesaian dari kongruensi linier 17x = 9 (mod 276).

Penyelesaian :

Karena 276 = 3 . 4 . 23, kongruensi linier 17x = 9 (mod 276) ekuivalen dengan sistem kongruensi berikut :

17x =9 (mod 3) atau x =0 (mod 3)

17x =9 (mod 4) x =1 (mod 4)

17x =9 (mod 23) 17x =9 (mod 23)

Berikutnya, pilih kongruensi linier yang paling sederhana yakni x = 0 (mod 3).

Selanjutnya, x = 0 (mod 3), maka berdasarkan definisi diperoleh x = 3k, k € Z.

Substitusikan x = 3k ke dalam kongruensi linier kedua yakni x = 1 (mod 4), sehingga diperoleh 3k = 1 (mod 4).

Selanjutnya, kalikan kedua ruas dengan 3 sehingga diperoleh 9k = k = 3 (mod 4).

Berdasarkan definisi, maka k = 3 (mod 4). k = 3 + 4l, l € Z.

Substitusikan k = 3 + 4l ke persamaan x = 3k, sehingga x = 3k = 3(3 + 4l) = 9 + 12l.

Substitusikan x = 9 + 12l ke kongruensi linier ketiga yakni 17x = 9 (mod 23), sehingga diperoleh :

17(9 + 12l) = 9 (mod 23).

204l = -144 (mod 23).

3l = 6 (mod 23).

l = 2 (mod 23).

Berdasarkan definisi l = 2 (mod 23). l = 2 + 23m, m € Z.

Substitusikan l = 2 + 23m ke dalam persamaan x = 9 + 12l.

Sehingga diperoleh :

x = 9 + 12(2 + 23m) = 33 + 276l.

x = 33 (mod 276)

jadi, solusi dari 17x = 9 (mod 276) adalah x = 33 (mod 276).

Dalil : Jika m₁, m₂, m₃, ... , m_r  Z+, dan (m_i,m_j) = 1 untuk i j, maka kongruensi simultan :

x  a₁ ( mod m₁)

x  a₂ ( mod m₂)

x  a₃ ( mod m₃)

.........................

.........................

x  a_r ( mod m_r)

Mempunyai penyelesaian persekutuan yang tunggal :

x    a_jb_j (mod [m₁,m₂,m₃,...,m_r]

Bukti :

Misal m = m₁, m₂, m₃, ... , m_r

Karena,  ( j = 1,2,3, ... , r) adalah bilangan bulat yang tidak memuat m_j, serta (m_i,m_j) =1 untuk i j maka  = 1.

Menurut dalil jika  = 1, maka kongruensi linear 1 (mod m_j) mempunyai 1 selesaian. Karena  masih memuat m_i, maka untuk i j

Berlaku   0 (mod m_j).

Dengan memilih t =  a_jb_j , maka

t =  +  + ... +  + ... +

Dalam modulo m_i (i=1,2,3,..., r) t dapat dinyatakan dengan

t  (  +  + ... +  + ... + ) (mod m_i)

t (mod m_i)+(mod m_i)+ ... + (mod m_i)+ ... +)(mod m_i)

Karena   1 (mod m_j) dan untuk i j berlaku   0 (mod m_j) maka diperoleh :   0 (mod mi) untuk i = 1,2,3,..., r.

Sehingga   0 (mod mi) untuk i = 1,2,3,..., r.

Jadi, t  0 (mod m_i) + 0 (mod m_i) + ...+ a_i (mod m_i) + ... + 0 (mod m_i)

         t  a_i (mod m_i).

Karena i = 1,2,3, ... , r maka

      t  a₁ (mod m₁)

      t  a₂ (mod m₂)

      t  a₃ (mod m₃)

     ......................

      t  a_r (mod m_r).

Hal ini berarti memenuhi semua kongruensi x  a_i (mod m_i). Dengan kata lain t merupakan selesaian persekutuan dari semua kongruensi linear simultan tersebut.

Contoh :

1. Tentukan penyelesaian kongruensi simultan linear berikut :

x  5 (mod 8)

x  3 (mod 7)

x  4 (mod 9)

Jawab :

Diketahui a₁ = 5, a₂ = 3, a₃ = 4 dan m₁ = 8, m₂ = 7, m₃ = 9.

Sehingga m = 8.7.9 = 504

(m₁,m₂) = 1, (m₁,m₃) = 1, (m₂,m₃) = 1.

Jadi kongruensi linear simultan memenuhi syarat untuk diselesaikan dengan teorema sisa China

  1 (mod m₁)   b₁  1 (mod 8)

                                   67 b₁  1 (mod 8)

                                        b₁  7

Dengan cara yang sama diperoleh b₂ = 4 dan b₃ = 5 

Jadi x =   a_jb_j

      x = 63.7.5 + 72.4.3 + 56.5.4

         = 4186

     x  4186 (mod [8.7.9])

     x   157 (mod 504)

2. Tentukan penyelesaian kongruensi

    19x  1 (mod 140)

Jawab :

Karena 140 = 4.5.7 , maka kongruensi dapat dipilah menjadi kongruensi   simultan yaitu

19x  1 (mod 4)

19x  1 (mod 5)

19x  1 (mod 7)

Selanjutnya dapat disederhanakan menjadi

    X  3 (mod 4)

    X  4 (mod 5)

    X  3 (mod 7)

Dengan cara seperti contoh 1 di atas diperoleh

x = 899

x  899 (mod 140)

x  59 (mod 140)

BAB III

PENUTUP

3.1.      Kesimpulan

Teorema Sisa Cina (Chinese Remainder Theorem) sudah ada sejak pertengahan abad pertama. Pada tahun 1809, ketika menganalisis batu yang disebut Pallas, Carl Friedrich Gauss menemukan kembali metode Cina yang telah ada sejak dulu yang dikenal dengan Teorema Sisa Cina. Pada abad ke-6, Teorema Sisa Cina telah digunakan dalam astronomi Cina kuno untuk mengukur pergerakan planet. Matematikawan yang terkenal adalah Qin Juishao.

Penerapan teorema sisa cina dalam menyelesaikan sistem persamaan linier non homogen dengan Algoritma Garner (Algoritma Garner bekerja dengan kongruen bilangan bulat modulo m. Bahwasanya Algoritma Garner digunakan untuk menyelesaikan masalah sisa Cina yang disajikan dalam teorema sisa Cina. Selanjutnya, algoritma Garner digunakan untuk menyelesaikan Sistem Persamaan Linier. Adapun sistem persamaan limier yang dimaksud adalah yang non homogen dengan konstanta bilangan bulat dan mempunyai penyelesaian tunggal).

Bentuk asli dari teorema ini, seperti terdapat dalam buku yang ditulis oleh ahli matematika dari Cina Qin Jiushao dan diterbitkan pada tahun 1247, adalah suatu pernyataan tentang kongruensi simultan.