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 a^k ≡ b^k (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!