ARDI KUSNADI

Minggu, 07 Maret 2021

SIFAT MODULO

Sifat 1 :

a ≡ a (mod n)
Jika a ≡ b (mod n) maka b ≡ a (mod n)
Jika a ≡ b (mod n) dan b ≡ c (mod n) maka a ≡ c (mod n)
Jika a ≡ b (mod n) dan c ≡ d (mod n) maka a + c = b + d (mod n)
Jika a ≡ b (mod n) dan c ≡ d (mod n) maka ac = bd (mod n)
Jika a ≡ b (mod n) maka a + c = b + c (mod n)
Jika a ≡ b (mod n) maka ac = bc (mod n)
Jika a ≡ b (mod n) maka ak ≡ bk (mod n) untuk k bilangan bulat positif sebarang.

Sifat 2 :

Jika ca ≡ cb (mod n) maka a ≡ b (mod n/d) dimana d = FPB (c, n)

Sifat 3 :

Jika ca ≡ cb (mod n) dan FPB(c, n) = 1 maka a ≡ b (mod n)

Sifat 4 :

Jika ca ≡ cb (mod p) dan p c, di mana p adalah bilangan prima maka a ≡ b (mod p)

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 b adalah sebuah bilangan bulat c dimana 0 ≤ c ≤ b-1, sehingga a-c adalah kelipatan b.
Contohnya, 7 mod 5 = 2, karena 7-2 adalah kelipatan 5. Perhatikan bahwa 7 mod 5 ≠ 12, karena 12 > 5, dan 7 mod 5 ≠ 3, karena 7-3 bukan kelipatan 5.
Bisa dibayangkan bahwa a mod b itu sisa pembagian dari a dibagi b. Tapi hati-hati untuk nilai a negatif: -7 mod 5 = 3.

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ᵇ) mod n = ((a mod n)ᵇ) 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
atau
phi(12)
= (2² - 2¹)(3 - 3⁰)
= (4 - 2)(3 - 1)
= (2)(2)
= 4

Teorema 3: Euler's theorem

Jika a adalah bilangan bulat, n adalah bilangan asli, dan a dan n saling relatif prima, maka a^phi(n) = 1 (mod n).
Digunakan bersama dengan a⁽ᵐⁿ⁾ = aᵐ * aⁿ untuk bilangan bulat a, m, n apapun, kita dapat menggunakan Euler's theorem untuk menyelesaikan beberapa soal.

Contoh soal:
Tentukan angka terakhir dari 2022²⁰²².

Solusi
2022²⁰²² mod 10
= (2022 mod 10)²⁰²² mod 10 (dari Teorema 1.3)
= 2²⁰²² mod 10
Perhatikan bahwa phi(10) = 10 * 1/2 * 4/5 = 4. Maka, 2022²⁰²² mod 10
= 2⁽²⁰²² ᵐᵒᵈ ᵖʰⁱ⁽¹⁰⁾⁾ mod 10 (dari Euler's theorem)
= 2⁽²⁰²² ᵐᵒᵈ ⁴⁾ mod 10
= 2² mod 10
= 4 mod 10
Jadi angka terakhir dari 2022²⁰²² adalah 4

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 2024²⁰²⁴.
Kita tidak boleh langsung memasukkan ke Euler's theorem.

Solusi salah
2024²⁰²⁴ mod 10
= 4²⁰²⁴ mod 10
Karena phi(10) = 4, maka 2024²⁰²⁴ mod 10
= 4⁽²⁰²⁴ ᵐᵒᵈ ⁴⁾ mod 10
= 4⁰ 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 = 2024²⁰²⁴, kita dapat:

2024²⁰²⁴ mod 2
= (2024 mod 2)²⁰²⁴ mod 2 (Teorema 1.3)
= 0²⁰²⁴ mod 2
= 0

Karena phi(5) = 4, maka:
2024²⁰²⁴ mod 5
= (2024 mod 5)⁽²⁰²⁴ ᵐᵒᵈ ᵖʰⁱ⁽⁵⁾⁾ mod 5 (Teorema 1.3 dan Euler's theorem)
= 4⁰ 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 2024²⁰²⁴ mod 10 = 6.

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

9 komentar:

Blog Guru Keren mengatakan...

Terima kasih Pak. Sangat bermanfaat

Unknown mengatakan...

Trimakasih sharing ilmunya pak..

Unknown mengatakan...

Terimaksih pak Ardi kalau bisa dibanyakin contoh soal dan pembahasnya y pak biar kita makin mantap mengerjakan soal2 modulus

Dinata mengatakan...

Terimakasih pak ardi... sangat membantu..

Unknown mengatakan...

Terima kasih pa ilmunya sangat membantu

rahma "ece" mengatakan...

Trima kasih pak atas ilmunya

Unknown mengatakan...

Terima Kasih Pak.

Ilmunya sangat membantu

Tissya Zainal mengatakan...

Terimakasih pak

Dini mengatakan...

Terimakasih pak..
Sangat bermanfaat..

Posting Komentar

TERIMAKASIH ATAS KUNJUNGANNYA