Kongruensi Modulo (2)


Pada tulisan sebelumnya yang berjudul Kongruensi Modulo (1) yaitu tulisan yang membahas tentang pengertian modulo dan beberapa sifat. Tentu sifat-sifat yang ada untuk mempermudah dalam mengerjakan soal. Nah, pada tulisan ini akan dikaji sifat tersebut dalam menyelesaiakan soal tentang modulo.

1.  Berapakah sisa dari 5 \cdot 5 \cdot 5 \cdot 5 \cdot 5 dibagi 11 ?

Penyelesaian :

Jelas bahwa 5 \equiv 5 (mod 11) karena 11 habis membagi (5 – 5).  Selanjutnya, dengan menggunkan sifat perkalian, diperoleh

5.5 \equiv 5.5 (mod 11)

5.5 \equiv 25 (mod 11)

5.5 \equiv (2.11 + 3) (mod 11)

5.5 \equiv 3 (mod 11)

5.5.5 \equiv 3.5 (mod 11)

5.5.5 \equiv 15 (mod 11)

5.5.5 \equiv (1.11 + 4) (mod 11)

5.5.5 \equiv 4 (mod 11)

5.5.5.5 \equiv 4.5 (mod 11)

5.5.5.5 \equiv 20 (mod 11)

5.5.5.5 \equiv (1.11 + 9) (mod 11)

5.5.5.5 \equiv 9 (mod 11)

5.5.5.5.5 \equiv 9.5 (mod 11)

5.5.5.5.5 \equiv 45 (mod 11)

5.5.5.5.5 \equiv (4.11 + 1) (mod 11)

5.5.5.5.5 \equiv 1 (mod 11)

Jadi 5.5.5.5.5 dibagi 11 sisanya 1

2.  Berapakah sisa pembagian dari (32+13)^2 dibagi 8?

Penyelesaian :

Perhatikan :

(32+13)^2 = 32^2 + 2 \cdot 32 \cdot 13 + 13^2

= 32^2 + 2 \cdot 32 \cdot 13 + 169

Karena 32 habis dibagi 8, berakibat 32^2 habis dibagi 8 dan 2 \cdot 32 \cdot 13 juga habis dibagi 8. Jadi jika ada perkalian yang merupakan faktor 8, jika dikali berapapun lalu di bagi 8 pasti tidak ada sisanya. Sehingga, kita tinggal memperhatikan 169, yaitu berapa sisa dari 169 dibagi 8. Jadi 169 mod 8 = (21.8 + 1) mod 8 = 1 mod 1. Jadi, (32+13)^2 dibagi 8 sisanya 1.

3.  Berapakah sisa 2^8-1 dibagi 5 ?

Penyelesaian :

Jelas bahwa 2 \equiv 2 (mod 5) karena 5 habis membgai (2 – 2). Selanjutnya, diperhatikan

2.2 \equiv 2.2 (mod 5)

2.2 \equiv 4 (mod 5)

2^2 \equiv 4 (mod 5)

2^2 \cdot 2^2 \equiv 4.4 (mod 5)

2^2 \cdot 2^2 \equiv 16 (mod 5)

2^2 \cdot 2^2 \equiv (1.15 + 1) (mod 5)

2^2 \cdot 2^2 \equiv 1 (mod 5)

2^4 \equiv 1 (mod 5)

2^4 \cdot 2^4 \equiv 16 (mod 5)

2^8 \equiv 1 (mod 5)

Selanjutnya, menggunakan sifat pengurangan

2^8-1 \equiv (1 – 1) (mod 5)

2^8-1 \equiv 0 (mod 5)

Jadi 2^8-1 dibagi 5 sisanya 0

4.  Berapa sisa 4.6 dibagi 5 ?

Penyelesaian :

(4.6) mod 5 = (5 – 1)(5 + 1) mod 5

= (5^2-1) mod 5

= –24 mod 5

= (-5.5 + 1) mod 5

= -1 mod 5

= (5 – 1) mod 5

= 4 mod 5

Jadi 4.6 dibagi 5 sisanya 4

5. Berapakah sisa 2^{17}+17^2 dibagi 9 ?

Penyelesaian :

Cara 1 :

Pada soal ini, terlebih dahulu bentuk kedalam bentuk modulo yaitu (2^{17} + 17^2) mod 9. Sebelum lebih jauh, ide mengerjakan soal ini adalah mulai dari mencari hasil dari 2^4 mod 9, selanjutnya 2^8 mod 9 dan 2^{16} mod 9 dengan memanfaatkan sifat perkalian.

2^4 mod 9 = 16 mod 9

= (9 + 7) mod 9

= 7 mod 9

2^8 mod 9 = 2^4 \cdot 2^4 mod 9

= 7 \cdot 7 mod 9

= 49 mod 9

= (5.9 + 4) mod 9

= 4 mod 9

2^{16} mod 9 = 2^8 \cdot 2^8 mod 9

= 4 \cdot 4 mod 9

= 16 mod 9

= (9 + 7) mod 9

= 7 mod 9

2^{17} mod 9 = 2^{16} \cdot 2 mod 9

= 7 \cdot 2 mod 9

= 14 mod 9

= (1.9 + 5) mod 9

= 5 mod 9

17^2 mod 9 = (17 mod 9 x 17 mod 9) mod 9

= ((9 + 8) mod 9 x (9 + 8) mod 9) mod 9

= (8 x 8) mod 9

= 64 mod 9

= (7.9 + 1) mod 9

= 1 mod 9

2^{17} + 17^2 mod 9 = 5 mod 9 + 1 mod 9

= 6 mod 9

= 6

Cara 2 :

(2^{17} + 17^2) mod 9 = (2 \cdot 2^16 + 17^2) mod 9

= (2 \cdot (2^8)^2 + 17^2) mod 9

= (2 \cdot 256^2 + 289) mod 9

= (2 \cdot (252+4)^2 + 289) mod 9

= (2 \cdot 4^2 +289) mod 9

= 321 mod 9

= (39.5 + 6) mod 9

= 6 mod 9

Jadi (2^{17} + 17^2) dibagi 9 sisanya 6

6. Berapa sisa 7^{77} dibagi 12 ?

Penyelesaian :

7^{77} mod 12 = 7 \cdot 7^{76} mod 12

= 7 \cdot (7^2)^{38} mod 12

= 7 \cdot 49^{38} mod 12

= 7 \cdot (4 \cdot 12 + 1)^{38} mod 12

= 7 \cdot 1^{38} mod 12

= 7 mod 12

= 7

Jadi 7^{77} dibagi 12 sisanya 7

7. Berapakah sisa pembagian dari 47^{99} oleh 100 ?

Penyelesaian :

Dalam soal ini akan dimanfaatkan sifat pekrkalian pada modulo.

47^2 = 2209 = 9 mod 100

47^3 = 103823 = 23 mod 100

(47^3)^3 = (23 mod 100)(23 mod 100)

= (23.23) mod 100

= 529 mod 100

= 29 mod 100

47^9 = 67 mod 100

47^{10} = 47 \cdot 47^{9}

= 47(49 mod 100)

= (47.29) mod 100

= 1363 mod 100

= 63 mod 100

47^{11} = 3 mod 100

47^{11} = 47 \cdot 47^{10}

= 47(63 mod 100)

= (47.63) mod 100

= 2961 mod 100

= 61 mod 100

47^{33} = (47^{11})^3

= (61.61.61) mod 100

= 226981 mod 100

= 81 mod 100

47^{99} = (47^{33})^3

= (81.81.81) mod 100

= 531441 mod 100

= 41 mod 100

Jadi 47^{99} dibagi 100 sisanya 41

8.  Berapakah sisa 3^{2001} dibagi 100?

Penyelesaian :

3^5 = 243 (mod 100)

= (2.100 + 43) (mod 100)

= 43 (mod 100)

3^{10} = (3^5)^2

= 43 \cdot 43 (mod 100)

= 1849 (mod 100)

= (18.100 + 49) (mod 100)

= 49 (mod 100)

3^{20} = (3^{10})^{2}

= 49 \cdot 49 (mod 100)

= 2401 (mod 100)

= (24.100 + 1) (mod 100)

= 1 (mod 100)

3^{2001} = 3^{20})^{100} \cdot 3

= (1^{100} \cdot 3$ (mod 100)

= 3 (mod 100)

Jadi 3^{2001} dibagi 100 sisanya 9

9.  Berapakah sisa dari 3^{2011}-1 dibagi 61 ?

Penyelesaian :

3^2 = 9 (mod 61)

3^4 = (3^2)^2

= 81 (mod 61)

= (1.61 + 20) (mod 61)

= 20 (mod 61)

3^8 = (3^4)^2

= 20 \cdot 20 (mod 61)

= 400 (mod 61)

= (5.61 + 34) (mod 61)

= 34 (mod 61)

3^{10} = 3^2 \cdot 3^8

= 9 \cdot 34 (mod 61)

= 306 (mod 61)

= (5.61 + 1) (mod 61)

= 1 (mod 61)

3^{2011} = 3^{2000 + 10 + 1}

= (3^{10})^{200} \cdot 3^{10} \cdot 3

= 1^{200} \cdot 1^{10} \cdot 3 (mod 61)

= 1 \cdot 1 \cdot 3 (mod 61)

= 3 (mod 61)

Karena 3^{2011} dibagi 61 sisanya 3, sehingga 3^{2011}-1 61 sisanya 2.

 

 

 

 

Iklan

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