KONSEP DAN TEOREMA MENGENAI MODULO

Konsep 1: Operasi modulo dalam matematika
Jika a adalah bilangan bulat dan b adalah bilangan asli (bulat positif), maka a mod badalah sebuah bilangan bulat c dimana ≤ c ≤ b-1, sehingga a-c adalah kelipatan b. Contohnya, 7 mod 3 = 1, karena 7-1 adalah kelipatan 3. Perhatikan bahwa 7 mod 3 != 4, karena 4 >= 3, dan 7 mod 3 != 2, karena 7-2 bukan kelipatan 3. Bisa dibayangkan bahwa a mod b itu sisa pembagian dari a dibagi b. Tapi hati-hati untuk nilai a negatif: -7 mod 3 = 2.


Teorema 1: Kumpulan sifat distributif mengenai modulo
Jika a, b adalah bilangan bulat dan n adalah bilangan asli, maka:
1. (a+b) mod n = (a mod n + b mod n) mod n
2. (ab) mod n = ((a mod n) * (b mod n)) mod n
3. (a^b) mod n = ((a mod n)^b) mod n, untuk b bilangan bulat nonnegatif

Konsep 2: Aritmatika modulo
a = b (mod c) berarti a mod c = b mod c.

Teorema 2: Invers modulo
Jika a adalah bilangan bulat dan n adalah bilangan asli, dan a, n saling relatif prima, maka terdapat sebuah nilai b sehingga ab = 1 mod n. Nilai b disebut invers dari a modulo n. 

Konsep 3: Euler's totient function (φ)
Jika n adalah bilangan asli, maka φ(n) adalah banyak bilangan asli ≤ n yang relatif prima dengan n. Misalnya, φ(12) = 4, karena di antara bilangan-bilangan asli ≤ 12 (yaitu 1,2,3,4,5,6,7,8,9,10,11,12), hanya ada empat buah (1,5,7,11) yang saling relatif prima dengan 12. Perhatikan bahwa φ(1) = 1, bukan 0.

Untuk selanjutnya, φ akan disebut "phi".

Teorema 2: Menghitung phi(n) dari faktorisasi prima n
Jika p1, p2, ..., pk adalah seluruh faktor prima dari n, maka phi(n) = n * (p1 - 1)/p1 * (p2 - 1)/p2 * ... * (pk - 1)/pk. Misalnya, karena faktor-faktor prima dari 12 adalah 2 dan 3, maka:

phi(12)
= 12 * (2-1)/2 * (3-1)/3
= 12 * 1/2 * 2/3
= 4

Teorema 3: Euler's theorem
Jika a adalah bilangan bulat, n adalah bilangan asli, dan a dan n saling relatif prima, makaa^phi(n) = 1 (mod n).

Digunakan bersama dengan a^(m+n) = a^m * a^n untuk bilangan bulat a,m,n apapun, kita dapat menggunakan Euler's theorem untuk menyelesaikan beberapa soal. Contoh:

Contoh soal: 
Tentukan angka terakhir dari 2013^2013.
Solusi
2013^2013 mod 10
= (2013 mod 10)^2013 mod 10 (dari Teorema 1.3)
= 3^2013 mod 10
Perhatikan bahwa phi(10) = 10 * 1/2 * 4/5 = 4. Maka, 2013^2013 mod 10
= 3^(2013 mod phi(10)) mod 10 (dari Euler's theorem)
= 3^(2013 mod 4) mod 10
= 3^1 mod 10
= 3 mod 10
= 3

Teorema 4: Chinese Remainder Theorem
Jika a1, a2, ..., ak adalah bilangan asli yang saling relatif prima, dan b1, b2, ..., bk adalah bilangan bulat, maka ada bilangan bulat x yang memenuhi:
x = b1 mod a1
x = b2 mod a2
...
x = bk mod ak
Selanjutnya, nilai x mod (a1*a2*...*ak) adalah unik.

Chinese Remainder Theorem (disingkat CRT) umumnya dipakai dimana Euler's theorem tidak dapat berjalan; saat a dan n tidak relatif prima.

Contoh soal :
Tentukan angka terakhir dari 2012^2012.
Kita tidak boleh langsung memasukkan ke Euler's theorem.

Solusi salah
2012^2012 mod 10
= 2^2012 mod 10
Karena phi(10) = 4, maka 2012^2012 mod 10
= 2^(2012 mod 4) mod 10
= 2^0 mod 10
= 1

Kita harus menggunakan cara lain. Biasanya, kita pakai CRT dengan cara ini.

Solusi benar
Berdasarkan CRT, kita dapat menentukan nilai dari mod 10 diberikan mod 2 dan mod 5. Untuk = 2012^2012, kita dapat:

2012^2012 mod 2
= (2012 mod 2)^2012 mod 2 (Teorema 1.3)
= 0^2012 mod 2
= 0

Karena phi(5) = 4, maka:
2012^2012 mod 5
= (2012 mod 5)^(2012 mod phi(5)) mod 5 (Teorema 1.3 dan Euler's theorem)
= 2^0 mod 5
= 1

Maka kita cari sebuah nilai x sehingga = 0 (mod 2) dan = 1 (mod 5). Didapat bahwa nilainya adalah = 6 (mod 10), sehingga 2012^2012 mod 10 = 6.

Selamat, sekarang Anda sudah dapat mengerjakan soal-soal modulo yang cukup umum!

Sumber : https://www.facebook.com/notes/osn-matematika

Nama saya Dan Lajanto, 

Silakan tanyakan saja untuk lebih lengkapnya ^^

Bagikan ini

Related Posts

Previous
Next Post »

4 komentar

komentar
June 16, 2016 at 12:40 PM delete

Pembuktian rumus distributif modulonya mana ? soalnya kan teorema jadi harus ada pembuktiannya. sekalian minta tolong referensi buku yang digunakan. Terima kasih sebelumnya

Reply
avatar
June 22, 2016 at 10:39 AM delete

untuk pembuktiannya sudah banyak di internet.. untuk buku referensi bisa search di google ...

Reply
avatar
September 30, 2016 at 8:36 AM delete

gan x = 0 (mod 2) dan x = 1 (mod 5) gimana caranya hingga dapat x = 6 (mod 10)? mohon pencerahan gan

Reply
avatar
September 30, 2016 at 12:31 PM delete

Maka kita cari sebuah nilai x sehingga x = 0 (mod 2) dan x = 1 (mod 5)
nilai x terkecil yang memenuhi adalah 6 karena 6 = 0 (mod 2) dan 6 = 1 (mod 5)
jadi jadi x akan bersisi 6 jika dibagi 10 ( x = 6 (mod 10))

Reply
avatar