Pengantar Teori Bilangan. Kuliah 10

Pengantar Teori Bilangan Kuliah 10

Materi Kuliah Chinese Remainder Theorem (Teorema Sisa Cina)

2/5/2014

Yanita, FMIPA Matematika Unand

2

Pengantar • Chinese Remainder Theorem (Teorema sisa Cina) adalah hasil tentang Kongruen di teori bilangan dan digeneralisasi dalam aljabar abstrak. • Pertama kali dipublikasikan pada abad ke-3 sampai abad ke-5 oleh Sun Tzu seorang matematikawan Cina. Pertama ditemukan pada teka-teki Cina kuno: Ada beberapa bilangan yang tidak diketahui. Bilangan itu dibagi 3, sisanya adalah 2; Bilangan itu dibagi oleh 5, sisanya adalah 3; Bilangan itu dibagi oleh 7 sisanya adalah 2; Bilangan yang manakah itu?

Dalam notasi matematika

2/5/2014

𝑥 = 2 (mod 3) 𝑥 = 3 (mod 5) 𝑥 = 2 (mod 7) Yanita, FMIPA Matematika Unand

3

Chinese Remainder Theorem Misalkan 𝑛1 , 𝑛2 , … , 𝑛𝑟 bilangan bulat positif sedemikian sehingga 𝑝𝑝𝑏 𝑛𝑖 , 𝑛𝑗 = 1 untuk 𝑖 ≠ 𝑗 . Maka system kongruen linier 𝑥 ≡ 𝑎1 (𝑚𝑜𝑑 𝑛1 ) 𝑥 ≡ 𝑎2 (𝑚𝑜𝑑 𝑛2 ) ⋮ 𝑥 ≡ 𝑎𝑟 (𝑚𝑜𝑑 𝑛𝑟 ) mempunyai solusi simultan, yang tunggal modulo bilangan bulat 𝑛1 𝑛2 … 𝑛𝑟 2/5/2014


4

Bukti Chinese Remainder Theoremn Bentuk hasilkali 𝑛 = 𝑛1 𝑛2 … 𝑛𝑟 . 𝑛

Untuk setiap 𝑘 = 1,2, … , 𝑟, misalkan 𝑁𝑘 = = 𝑛1 𝑛2 … 𝑛𝑘−1 𝑛𝑘+1 … 𝑛𝑟 . Atau, 𝑁𝑘 adalah hasilkali semua bilangan bulat 𝑛𝑖 dengan 𝑛𝑘 factor 𝑛𝑘 dihapuskan. Diketahui bahwa 𝑝𝑝𝑏 𝑛𝑖 , 𝑛𝑗 = 1 untuk 𝑖 ≠ 𝑗 atau 𝑛𝑖 relative prima dengan 𝑛𝑗 untuk 𝑖 ≠ 𝑗 . 𝑝𝑝𝑏 𝑁𝑘 , 𝑛𝑘 = 1.

Dengan demikian diperoleh

Berdasarkan teori kongruen linier tunggal, hal ini memungkinkan untuk menyelesaikan kongruen 𝑁𝑘 𝑥 ≡ 1 (mod 𝑛𝑘 ), sebutlah solusi tunggal 𝑥𝑘 . Tujuannya adalah untuk membuktikan bahwa bilangan 𝑥 = 𝑎1 𝑁1 𝑥1 + 𝑎2 𝑁2 𝑥2 + ⋯ + 𝑎𝑟 𝑁𝑟 𝑥𝑟 = 𝑎𝑘 𝑁𝑘 𝑥𝑘 (𝑚𝑜𝑑 𝑛𝑘 )

adalah solusi simultan dari system kongruen linier yg diberikan. Pertama, amati bahwa 𝑁𝑖 ≡ 0 (mod 𝑛𝑘 ) untuk 𝑖 ≠ 𝑘, karena 𝑛𝑘 |𝑁𝑖 Hasilnya adalah 𝑥 = 𝑎1 𝑁1 𝑥1 + 𝑎2 𝑁2 𝑥2 + ⋯ + 𝑎𝑟 𝑁𝑟 𝑥𝑟 = 𝑎𝑘 𝑁𝑘 𝑥𝑘 (𝑚𝑜𝑑 𝑛𝑘 ) Tapi 𝑥𝑘 bilangan bulat yang dipilih untuk memenuhi kongruen 𝑁𝑘 𝑥 ≡ 1 (mod 𝑛𝑘 ), yang menyebabkan 𝑥 ≡ 𝑎𝑘 . 1 ≡ 𝑎𝑘 (mod 𝑛𝑘 ) Ini menunjukkan bahwa solusi untuk system kongruen yang diberikan ada. Untuk menunjukkan ketuanggalannya, misalkan 𝑥′ adalah sebarang bilangan bulat yang memenuhi system kongruen ini. Maka 𝑥 ≡ 𝑎𝑘 ≡ 𝑥′ (mod 𝑛𝑘 )

dan selanjutnya 𝑛𝑘 |𝑥 − 𝑥′ untuk setiap nilai 𝑘 . 𝑥′ (mod 𝑛𝑘 ).

𝑘 = 1,2, … , 𝑟

Karena 𝑝𝑝𝑏 𝑛𝑖 , 𝑛𝑗 = 1, maka diperoleh 𝑛1 𝑛2 … 𝑛𝑟 |𝑥 − 𝑥′, karenanya 𝑥 ≡ 5

Dengan Chinese Remainder Theorem, maka langkah penyelesaian suatu system kongruen linier adalah: Misalkan system kongruen linier 𝑥 ≡ 𝑎1 (𝑚𝑜𝑑 𝑛1 ) 𝑥 ≡ 𝑎2 (𝑚𝑜𝑑 𝑛2 ) ⋮ 𝑥 ≡ 𝑎𝑟 (𝑚𝑜𝑑 𝑛𝑟 ) Maka langkah untuk mencari solusi system ini: 1. Periksa 𝑝𝑝𝑏(𝑛𝑖 , 𝑛𝑗 ) untuk 𝑖 ≠ 𝑗, jika 𝑝𝑝𝑏 𝑛𝑖 , 𝑛𝑗 = 1 maka system punya solusi.

2. Tentukan 𝑛 = 𝑛1 𝑛2 … 𝑛𝑟 dan 𝑁𝑘 =

𝑛 𝑛𝑘

= 𝑛1 𝑛2 … 𝑛𝑘−1 𝑛𝑘+1 … 𝑛𝑟 , 𝑘 = 1,2, … , 𝑟.

3. Selesaikan 𝑁𝑘 𝑥𝑘 ≡ 1 (mod 𝑛𝑘 ), 𝑘 = 1,2, … , 𝑟. 4. Solusinya adalah 𝑥 ≡ (𝑎1 𝑁1 𝑥1 + 𝑎2 𝑁2 𝑥2 + ⋯ + 𝑎𝑟 𝑁𝑟 𝑥𝑟 ) (𝑚𝑜𝑑 𝑛)

2/5/2014


6

Contoh 1 Dengan Chinese Remainder Theorem, carilah solusi untuk system kongruen linier berikut: 𝑥 ≡ 3 (mod 4) 𝑥 ≡ 2 (mod 3) 𝑥 ≡ 4(mod 5) Perhatikan bahwa system ini terdiri dari 3 persamaan konruen linier, jadi 𝑘 = 1,2,3. Dari system diperoleh 𝑎1 = 3, 𝑎2 = 2, 𝑎3 = 4, 𝑛1 = 4, 𝑛2 = 3, 𝑛3 = 5. 1. Oleh karena 𝑝𝑝𝑏 4,3 = 𝑝𝑝𝑏 4,5 = 𝑝𝑝𝑏 3,5 = 1, maka system ini punya solusi. 2. Nilai 𝑛 = 𝑛1 𝑛2 𝑛3 = 4.3.5 = 60 dan 𝑛

60 4

= 15;

2

60 3

= 20;

𝑛 𝑛3

60 5

= 12.

𝑁1 = 𝑛 = 1

𝑛

𝑁2 = 𝑛 = 𝑁3 = 3. Selesaikan 15𝑥1 ≡ 1 20𝑥2 ≡ 1 12𝑥3 ≡ 1

=

Dengan menggunakan solusi dalam persamaan kongruen linier, maka solusi untuk 15𝑥1 ≡ 1 mod 4 adalah : 15𝑥1 ≡ 1 mod 4 ekivalen dengan 15𝑥1 − 1 = 4𝑘 . 1+4𝑘 Diperoleh 𝑥1 = 15 . Nilai 𝑘 = 11 menyebakan 𝑥1 = 3. Dengan cara yang sama, diperoleh 𝑥2 = 2, dan 𝑥3 = 3. 4. Solusinya adalah 𝑥 = (𝑎1 𝑁1 𝑥1 + 𝑎2 𝑁2 𝑥2 + 𝑎3 𝑁3 𝑥3 ) (mod 𝑛) = (3.15.3 + 2.20.2 + 4.12.3) (mod 60) = 359 (𝑚𝑜𝑑 60) = 59 (𝑚𝑜𝑑 60)

𝑁𝑘 𝑥𝑖 ≡ 1 (mod 𝑛𝑘 ), 𝑘 = 1,2,3, yaitu mod 4 mod 3 mod 5

Jadi solusi untuk 𝑥 ≡ 3 (mod 4) 𝑥 ≡ 2 (mod 3) 𝑥 ≡ 4(mod 5) adalah 𝑥 ≡ 59 (mod 60)


7

Contoh 2 Dengan menggunakan Chinese Remainder Theorem, carilah solusi untuk system kongruen linier berikut: 𝑥 = 2 (mod 3) 𝑥 = 3 (mod 5) 𝑥 = 2 (mod 7) Perhatikan bahwa system ini terdiri dari 3 persamaan konruen linier, jadi 𝑘 = 1,2,3. Dari system diperoleh 𝑎1 = 2, 𝑎2 = 3, 𝑎3 = 2, 𝑛1 = 3, 𝑛2 = 5, 𝑛3 = 7.

1. Oleh karena 𝑝𝑝𝑏 3,5 = 𝑝𝑝𝑏 3,7 = 𝑝𝑝𝑏 5,7 = 1 , maka system ini punya solusi. 2. Nilai 𝑛 = 𝑛1 𝑛2 𝑛3 = 3.5.7 = 105 dan 𝑁1 =

𝑛 𝑛1

𝑁2 =

𝑛 𝑛2

𝑁3 =

𝑛 𝑛3

=

105 3

= 35;

=

105 5

= 21;

=

105 7

= 15.

Dengan menggunakan solusi dalam persamaan kongruen linier, maka solusi untuk 35𝑥1 ≡ 1 mod 3 adalah :

35𝑥1 ≡ 1 mod 3 ekivalen dengan 35𝑥1 − 1 = 3𝑘. 1+3𝑘 Diperoleh 𝑥1 = 35 . Nilai 𝑘 = 23 menyebakan 𝑥1 = 2. Dengan cara yang sama, diperoleh 𝑥2 = 1, dan 𝑥3 = 1. 4. Solusinya adalah 𝑥 ≡ (𝑎1 𝑁1 𝑥1 + 𝑎2 𝑁2 𝑥2 + 𝑎3 𝑁3 𝑥3 ) (mod 𝑛) ≡ (2.35.2 + 3.21.1 + 2.15.1) (mod 105) ≡ 233 (mod 105) ≡ 23 (mod 105) Jadi solusi untuk 𝑥 ≡ 3 (mod 4) 𝑥 ≡ 2 (mod 3) 𝑥 ≡ 4(mod 5)

3. Selesaikan 𝑁𝑘 𝑥𝑘 ≡ 1 (mod 𝑛𝑘 ), 𝑘 = 1,2,3, yaitu 35𝑥1 ≡ 1(mod 3) adalah 𝑥 ≡ 23 (mod 105) 21𝑥2 ≡ 1 (mod 5) 15𝑥3 ≡ 1 (mod 7) Yanita, FMIPA Matematika Unand

8

Dengan Chinese Remainder Theorem, langkah penyelesaian jika persamaan kongruen linier yang diketahui: 1. Dari persamaan kongruen linier 𝑎𝑥 ≡ 𝑏 (mod 𝑛), maka cari faktorisasi prima dari 𝑛, yaitu 𝑛 = 𝑛1 𝑛2 … 𝑛𝑟 dengan 𝑛𝑖 adalah prima, 𝑖 = 1,2, … 𝑟 2. Selesaikan system 𝑎𝑎𝑘 ≡ 𝑏 (mod 𝑛𝑖 ) , 𝑘 = 1,2, … , 𝑟 . Untuk mendapatkan nilai 𝑎𝑖 . 𝑛 𝑛𝑘

3. Cari 𝑁𝑘 = dengan 𝑘 = 1,2, … , 𝑟 dan selesaikan system 𝑁𝑘 𝑥𝑘 ≡ 1 (mod 𝑛𝑘 ) untuk mendapatkan nilai 𝑥𝑘 . 4. Solusinya adalah 𝑥 ≡ (𝑎1 𝑁1 𝑥1 + 𝑎2 𝑁2 𝑥2 + ⋯ + 𝑎𝑟 𝑁𝑟 𝑥𝑟 ) (mod 𝑛) 2/5/2014


9

Contoh 3: Selesaikan persamaan linier kongruen 17𝑥 ≡ 9 mod 276 dengan dua cara. Dengan cara biasa (solusi persamaan kongruen linier),

1.

𝑝𝑝𝑏 17,276 = 1

2.

Persamaan 17𝑥 ≡ 9 mod 276 ekivalen dengan 17𝑥 − 276𝑘 = 9 atau 9+276𝑘 diperoleh 𝑥 = . Nilai 𝑘 = 2 , 17 menyebabkan 𝑥 = 33

3.

Solusinya adalah 𝑥 ≡ 33 (mod 276)

2/5/2014

Dengan Chinese Remainder Theorem, 1. faktorisasi prima dari 276 adalah 22 . 3.23. Jadi 276 = 3.4.23. Dengan demikian diperoleh 𝑛 = 276, 𝑛1 = 3, 𝑛2 = 4, 𝑛3 = 23. 2. Selesaikan system 17𝑎𝑘 ≡ 9 (mod 𝑛𝑘 ) , 𝑘 = 1,2,3, yaitu system 17𝑎1 ≡ 9 (𝑚𝑜𝑑 3) 𝑎1 = 3 17𝑎2 ≡ 9 (𝑚𝑜𝑑 4) Diperoleh: 𝑎2 = 5 17𝑎3 ≡ 9 (𝑚𝑜𝑑 23) 𝑎3 = 10 3. Cari nilai 𝑁𝑘 = 276 3

𝑛 𝑛𝑘

𝑛 𝑛2

𝑛

dengan 𝑘 = 1,2,3, yaitu 𝑁1 = 𝑛 = 276 4

𝑛 𝑛3

276 23

= 92; 𝑁2 = = = 69; 𝑁3 = = = 12. Selesaikan system 𝑁𝑘 𝑥𝑘 ≡ 1 (mod 𝑛𝑘 ), yaitu: 92𝑥1 ≡ 1 (𝑚𝑜𝑑 3) 𝑥1 = 2 69𝑥2 ≡ 1 (𝑚𝑜𝑑 4) Diperoleh 𝑥2 = 1 12𝑥3 ≡ 1 (𝑚𝑜𝑑 23) 𝑥3 = 2 4. Solusinya adalah 𝑥 ≡ (𝑎1 𝑁1 𝑥1 + 𝑎2 𝑁2 𝑥2 + 𝑎3 𝑁3 𝑥3 ) (mod 𝑛) 𝑥 ≡ (3.92.2 + 5.69.1 + 10.12.2)(mod 276) 𝑥 ≡ 1137 (mod 276) 𝑥 ≡ 33 (mod 276)


10

1

Contoh 4: Selesaikan persamaan linier kongruen 13𝑥 ≡ 1 mod 70 dengan dua cara.

Dengan cara biasa (solusi persamaan kongruen linier), 1. 𝑝𝑝𝑏 13,70 = 1 2. Persamaan 13𝑥 ≡ 1 mod 70 ekivalen dengan 13𝑥 − 70𝑘 = 1 atau diperoleh 1+70𝑘 𝑥= . Nilai 𝑘 = 5 , 13 menyebabkan 𝑥 = 27 3. Solusinya adalah 𝑥 ≡ 27 (mod 70)

2/5/2014

Dengan Chinese Remainder Theorem, 1. faktorisasi prima dari 70 adalah 2.5.7. Jadi 70 = 2.5.7. Dengan demikian diperoleh 𝑛 = 70, 𝑛1 = 2, 𝑛2 = 5, 𝑛3 = 7. 2. Selesaikan system 13𝑎𝑘 ≡ 1 (mod 𝑛𝑘 ) , 𝑘 = 1,2,3, yaitu system 13𝑎1 ≡ 1 (𝑚𝑜𝑑 2) 𝑎1 = 1 13𝑎2 ≡ 1 (𝑚𝑜𝑑 5) Diperoleh: 𝑎2 = 2 13𝑎3 ≡ 1 (𝑚𝑜𝑑 7) 𝑎3 = 6 𝑛

3. Cari nilai 𝑁𝑘 = 𝑛 35; 𝑁2 =

𝑛 𝑛2

=

70 𝑘 = 5

𝑛

dengan 𝑘 = 1,2,3, yaitu 𝑁1 = 𝑛 = 𝑛 𝑛3

70 7

14; 𝑁3 = = = 10. Selesaikan system 𝑁𝑘 𝑥𝑘 ≡ 1 (mod 𝑛𝑘 ), yaitu: 35𝑥1 ≡ 1 (𝑚𝑜𝑑 2) 𝑥1 = 1 14𝑥2 ≡ 1 (𝑚𝑜𝑑 5) Diperoleh 𝑥2 = 4 10𝑥3 ≡ 1 (𝑚𝑜𝑑 7) 𝑥3 = 5

1

70 2

=

4. Solusinya adalah 𝑥 ≡ (𝑎1 𝑁1 𝑥1 + 𝑎2 𝑁2 𝑥2 + 𝑎3 𝑁3 𝑥3 ) (mod 𝑛) 𝑥 ≡ (1.35.2 + 2.14.4 + 6.10.5)(mod 70) 𝑥 ≡ 447 (mod 70) 𝑥 ≡ 27 (mod 70)


11

Solusi Sistem Kongruen Linier dengan dua Variabel Definisi Persamaan kongruen linier dengan dua variabel adalah persamaan dalam bentuk 𝑎𝑥 + 𝑏𝑦 ≡ 𝑐 mod 𝑛 , dengan 𝑥, 𝑦 ∈ ℤ. Teorema 4.9 Sistem kongruen linier 𝑎𝑥 + 𝑏𝑦 ≡ 𝑟 mod 𝑛 c𝑥 + 𝑑𝑦 ≡ 𝑠 mod 𝑛 mempunyai solusi tunggal modulo 𝑛 jika 𝑝𝑝𝑏 𝑎𝑑 − 𝑏𝑐, 𝑛 = 1 2/5/2014


12

Bukti Teorema 4.9 Diketahui system kongruen linier 𝑎𝑥 + 𝑏𝑦 ≡ 𝑟 mod 𝑛 c𝑥 + 𝑑𝑦 ≡ 𝑠 mod 𝑛 Dengan 𝑝𝑝𝑏 𝑎𝑑 − 𝑏𝑐, 𝑛 = 1. Akan dibuktikan system ini mempunyai solusi tunggal modulo 𝑛. Misalkan 𝑎𝑥 + 𝑏𝑦 ≡ 𝑟 mod 𝑛 … (1) c𝑥 + 𝑑𝑦 ≡ 𝑠 mod 𝑛 … (2) Kalikan persamaan (1) dengan 𝑑, dan persamaan (2) dengan 𝑏, maka diperoleh 𝑑(𝑎𝑥 + 𝑏𝑦) ≡ 𝑑𝑟 mod 𝑛 … (1′) 𝑏(c𝑥 + 𝑑𝑦) ≡ 𝑏𝑠 mod 𝑛 … (2′) Jika pers (1′) dikurangkan dengan pers (2′) maka diperoleh 𝑑𝑎𝑥 − 𝑏𝑐𝑥 ≡ 𝑑𝑟 − 𝑏𝑠 (mod 𝑛) atau 𝑎𝑑 − 𝑏𝑐 𝑥 ≡ 𝑑𝑟 − 𝑏𝑠 (mod 𝑛) … (3) Oleh karena 𝑝𝑝𝑏 𝑎𝑑 − 𝑏𝑐, 𝑛 = 1, maka dijamin bahwa 𝑎𝑑 − 𝑏𝑐 𝑧 ≡ 1 (mod 𝑛) mempunyai solusi tunggal; misalkan solusi tersebut adalah 𝑡. 2/5/2014

Jika persamaan (3) dikalikan dengan 𝑡, diperoleh 𝑥 ≡ 𝑡 𝑑𝑟 − 𝑏𝑠 (mod 𝑛). Dengan cara yang sama dapat dicari nilai 𝑦, yaitu Kalikan persamaan (1) dengan 𝑐, dan persamaan (2) dengan 𝑎, maka diperoleh 𝑐(𝑎𝑥 + 𝑏𝑦) ≡ 𝑐𝑟 mod 𝑛 … (1′′) 𝑎(c𝑥 + 𝑑𝑦) ≡ 𝑎𝑠 mod 𝑛 … (2′′) Jika pers (1′′) dikurangkan dengan pers (2′′) maka diperoleh 𝑐𝑎𝑥 − 𝑏𝑐𝑦 ≡ 𝑎𝑠 − 𝑐𝑟 (mod 𝑛) atau 𝑎𝑑 − 𝑏𝑐 𝑦 ≡ (𝑎𝑠 − 𝑐𝑟)(mod 𝑛) … (3′) Oleh karena 𝑝𝑝𝑏 𝑎𝑑 − 𝑏𝑐, 𝑛 = 1, maka dijamin bahwa 𝑎𝑑 − 𝑏𝑐 𝑧 ≡ 1 (mod 𝑛) mempunyai solusi tunggal; misalkan solusi tersebut adalah 𝑡′. Jika persamaan (3′) dikalikan dengan 𝑡′, diperoleh 𝑦 ≡ 𝑡′ 𝑎𝑠 − 𝑐𝑟 (mod 𝑛).


13

Contoh Carilah solusi untuk sitem kongruen linier: 7𝑥 + 3𝑦 ≡ 10 mod 16 … (1) 2𝑥 + 5𝑦 ≡ 9 mod 16 … (2) Penyelsaian Dari system tersebut diperoleh 𝑎 = 7, 𝑏 = 3, 𝑐 = 2, 𝑑 = 5, 𝑟 = 10, 𝑠 = 9 dan 𝑛 = 16 Perhatikan bahwa 𝑝𝑝𝑏 𝑎𝑑 − 𝑏𝑐, 𝑛 = 𝑝𝑝𝑏 7.5 − 3.2,16 = 𝑝𝑝𝑏 29,16 = 1, maka system ini punya solusi. Kemudian dengan metode eliminasi, untuk mencari nilai 𝑥:

Mencari nilai 𝑦

Persamaan 29𝑦 ≡ 43 (𝑚𝑜𝑑 16) ekivalen dengan 29𝑦 − 43+16𝑘 16𝑘 = 43 atau 𝑥 = . Nilai 𝑘 = 10 menyebabkan nilai 29 𝑥 = 7. Jadi solusi untuk 29𝑦 ≡ 43 (mod 16) adalah 𝑦 ≡ 7 (mod 16).

Dengan solusi untuk persamaan kongruen linier, 29𝑥 ≡ 23 (𝑚𝑜𝑑 16) ekivalen dengan 29𝑥 − 16𝑘 = 23 atau 23+16𝑘 𝑥= . Nilai 𝑘 = 4 menyebabkan 𝑥 = 3. Jadi solusi 29 untuk 29𝑥 ≡ 23 (mod 16) adalah 𝑥 ≡ 3 (mod 16) 2/5/2014

Jadi solusi untuk system adalah 𝑥 ≡ 3 (mod 16) 𝑦 ≡ 7 (mod 16)


14

Latihan 1. Carilah solusi untuk system 𝑥 ≡ 5 mod 11 𝑥 ≡ 14 (mod 29) 𝑥 ≡ 15 (mod 31) 2. Selesaikan dengan 2 cara (solusi persamaan kongruen linier dan Chinese Remainder Theorem) persamaan 17𝑥 ≡ 3 mod 210 . 3. Carilah solusi untuk system 3𝑥 + 4𝑦 ≡ 5 mod 13 2𝑥 + 5𝑦 ≡ 7 mod 13 2/5/2014

selesai 4 Mei 2014

15

Pengantar Teori Bilangan. Kuliah 10

Recommend Documents