Page 16 - Deborah Pardosi_2113150011_E-book

Kekongruenan dalam konsep modulo berkaitan erat dengan alogaritma pembagian. Misal a ∈
Bilangan bulat, b ∈ Bilangan bulat, dan a ≠ 0. Maka terdapat q, r ∈ Bilangan bulat sedemikian
sehingga b = qa + r, 0 ≤ r < a.

Terdapat teorema-teorema dalam kekongruenan konsep modulo pada bilangan bulat. Yakni:
1. Teorema 1
a ≡ b (mod m) jika a dan hanya jika terdapat suatu k ∈ Bilangan bulat sedemikian sehingga
a = mk + b.
2. Teorema 2
Jika m ∈ Bilangan bulat dan a, b, c ∈ Bilangan bulat, maka kekongruenan modulo m
memenuhi:
a. Sifat refleksi : a ≡ a (mod m)
b. Sifat simetris : jika a ≡ b (mod m), maka b ≡ a (modd m).
c. Sifat transitif : jika a ≡ b (mod m) dan b ≡ c (mod m), maka a ≡ c (mod m).
3. Teorema 3
Jika a ≡ b (mod m), maka:
a. a + c ≡ b + c (mod m)
b. ac ≡ bc (mod m)
c. ac ≡ bc (mod mc)
4. Teorema 4
Jika a ≡ b (mod m) dan c ≡ d (mod m), maka:
a. a + c ≡ b + d (mod m)
b. ac ≡ bd (mod m)
5. Teorema 5
Jika a ≡ b (mod m) dan c ≡ d (mod m) maka untuk sebarang x ∈ Bilangan bulat dan y ∈
Bilangan bulat. Maka ax = cy ≡ bx + dy (mod m).
6. Teorema 6
Residu terkecil
Jika a ≡ r (mod m) dengan 0 ≤ r < m, maka r disebut residu terkecil dari a modulo m. untuk
kekongruenan moduo m, himpunan {0, 1, 2, 3, …, m – 1} disebut himpunan residu terkecil.
7. Teorema 7
a ≡ b (mod m) jika dan hanyajika a dan b ketika dibagi m memiliki sisa pembagian yang
sama.
Sistem residu lengkap
Himpunan {r1, r2, r3, …, rm} disebut sistem residu lengkap modulo m jika setiap r ∈ {r1,
r2,r3, … rm} kongruen dengan satu dan hanya satu dari 0, 1, 2, …, m – 1.
8. Teorema 8
Jika ac ≡ bc (mod m) dan (c, m) = 1 maka a ≡ b (mod m).
9. Teorema 9

Jika ac ≡ bc (mod m) dan (c, m) dan (cm) = d maka a ≡ b (mod )

10. Teorema 10
Jika a ≡ b (mod m) dan n ∈ Bilangan bulat maka a ≡ b (mod m).
n
n
+

12