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 0 ≤ 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 x mod 10 diberikan x mod 2 dan x mod 5. Untuk x = 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 x = 0 (mod 2) dan x = 1 (mod 5). Didapat bahwa nilainya adalah x = 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