SIFAT-SIFAT OPERASI HIMPUNAN

BILANGAN PRIMA

          Jika p bilangan bulat, p¹0 dan p¹1 hanya mempunyai pembagi 1 dan p, maka p disebut bilangan prima. Bilangan bulat selain bilangan prima disebut bilangan komposit.

Contoh bilangan-bilangan  prima: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, …. Contoh bilangan-bilangan komposit: 4, 6, 8, 9, 10, 12, 14, 15, 16, 18, 20, 21, 22, 24, 25, 26, 27, 28, 30, 32, 33, 34, 35, 36, …

Teorema: Jika p prima dan pï(a.b), maka pïa atau pïb.

PEMBAGI

Bilangan bulat a adalah pembagi dari b (a¹0), jika ada bilangan bulat c sedemikian sehingga b=a.c. Simbol: aïb. Bilangan bulat b disebut kelipatan dari a dan bilangan a disebut faktor dari b.

          Contoh: 3ï12, -3ï6, aï0.

KAWAN (ASSOCIATES)

          Dua bilangan bulat tak nol, a dan b adalah sekawan, jika aïb dan bïa. Contoh: bilangan bulat a dan –a.

FPB (Faktor Persekutuan terBesar)

          Jika aïb dan aïc, maka a disebut faktor persekutuan dari b dan c (a¹0). Contoh: 2ï8 dan 2ï12, maka 2 adalah faktor persekutuan 8 dan 12.

          Bilangan bulat d (d¹0) disebut FPB dari a dan b, jika memenuhi dua syarat:

1.   dïa dan dïb.

2.   setiap faktor persekutuan dari a dan b adalah pembagi dari bilangan bulat d.

Contoh:

Carilah FPB dari 595 dan 252.

Kelipatan Persekutuan terKecil (KPK)

Perhatikan kelipatan dari 12, yakni 12, 24, 36, 48, 60, 72,  …

Perhatikan kelipatan dari 18, yakni 18, 36, 54, 72, 90,  …

Perhatikan juga bahwa kelipatan persekutuan antara 12 dan 18 adalah 36, 72, …., dan bahwa kelipatan persekutuan yang terkecil adalah 36.

          Cobalah cari FPB dan KPK dari 12 dan 18 dengan cara faktorisasi prima. Juga FPB dan KPK dari 595 dan 252.

ALGORITMA PEMBAGIAN

Jika a sembarang bilangan bulat dan b¹0, maka ada dua bilangan bulat q dan r, sedemikian sehingga a=b.q+r. Dalam hal ini a disebut yang dibagi, b disebut pembagi, q disebut hasil bagi, dan r > 0 disebut sisa pembagian.

Contoh-contoh:

13 = 5*2 + 3. Bilangan 13 disebut yang dibagi, 5 adalah pembagi, 2 adalah hasil bagi, dan 3 adalah sisa pembagian.

ALGORITMA EUCLID

          Algoritma Euclid digunakan untuk mencari FPB dua buah bilangan bulat (positif) a dan b.

          Prosesnya:

a = b.q₁ + r₁

b = r₁.q₂ + r₂

r₁ = r₂.q₃ + r₃

r₂ = r₃.q₄ + r₄

…….

…….

r_k = r_k+1.q_k+2 + 0

Maka FPB = r_k+1.

Contoh:

FPB dari 595 dan 252.

595 = 252.2 + 91

252 = 91.2 + 70

91 = 70.1 + 21

70 = 21.3 + 7

21 = 7.3 + 0

FPB = 7

Cobalah nyatakan 7 sebagai kombinasi linier dari 595 dan 252.

FAKTORISASI UNIK

Teorema:

Setiap bilangan bulat n, yang lebih besar dari pada satu, dapat dituliskan secara unik sebagai hasil kali dari bilangan-bilangan prima, kecuali urutannya.

KONGRUEN MODULO

Dari contoh di atas, 13 dibagi 5 memberikan hasil bagi 2 dengan sisa pembagian 3. Dengan kata lain: 13 mod 5 = 3, atau 13 º 3 (mod 5); dibaca: 13 kongruen dengan 3 modulo 5.

Contoh lain: 26 mod 5 = 1, atau 26 º 1 (mod 5); dibaca: 26 kongruen dengan 1 modulo 5.

Buktikan relasi “kongruen modulo” adalah relasi ekuivalen.

         

KELAS EKUIVALEN

Misalkan A himpunan tak kosong, dan R relasi ekuivalen pada A. Misalkan aÎA. Elemen xÎA yang memenuhi xRa atau (x,a)ÎR akan membentuk suatu subset A_a dari A yang disebut kelas ekuivalen.

Notasi: A_a = [a] = {x / xÎA, (x,a)ÎR}.

Contoh:

·        A = {segitiga pada suatu bidang rata} dan R adalah relasi ekuivalen “x sama dan sebagun dengan y”.  Ambillah aÎA suatu segitiga. Kelas ekuivalen [a] adalah himpunan semua segitiga di A yang sama dan sebangun dengan segitiga a.

·        Misalkan Z={bilangan bulat}, Z₀ adalah himpunan bilangan-bilangan bulat yang habis dibagi 5, Z₁ adalah himpunan bilangan-bilangan bulat yang bila dibagi 5 bersisa 1, Z₂ adalah bilangan-bilangan bulat yang bila dibagi 5 bersisa 2, Z₃ adalah bilangan-bilangan bulat yang bila dibagi 5 bersisa 3, dan Z₄ adalah bilangan-bilangan bulat yang bila dibagi 5 bersisa 4.

Z₀ = { …, -10, -5, 0, 5, 10, …}

Z₁ = { …, -9, -4, 1, 6, 11, … }

Z₂ = { …, -8, -3, 2, 7, 12, … }

Z₃ = { …, -7, -2, 3, 8, 13, … }

Z₄ = { …, -6, -1, 4, 9, 14, … }

Sifat-sifat Kelas Ekuivalen

1.   Gabungan seluruh kelas ekuivalen = A

2.   Dua kelas ekuivalen adalah sama, atau saling lepas.

3.   Relasi ekuivalen R membentuk partisi dari A; sebaliknya, partisi mendefinisikan relasi ekuivalen di A.

Contoh:

Perhatikan Z₀, Z₁, Z₂, Z₃, dan Z₄ dari contoh di atas, bila digabungkan akan menjadi Z, yakni himpunan bilangan bulat. Z₀, Z₁, Z₂, Z₃, dan Z₄ adalah saling lepas dan membentuk partisi pada himpunan bilangan bulat Z.

HIMPUNAN KUOSIEN (QUOTIENT SET)

Misalkan A himpunan tak kosong dan R relasi ekuivalen pada A. Notasi A/R = adalah himpunan kelas-kelas ekuivalen yang saling lepas.

Contoh:

Z = {bilangan bulat} dan R adalah relasi ekuivalen “kongruen modulo 5”. Z/R = {Z₀, Z₁, Z₂, Z₃, dan Z₄} = {[0], [1], [2], [3], [4]}.

OPERASI BINER

Misalkan A himpunan tak kosong. Operasi biner pada himpunan A adalah pemetaan f: AxA®A sebagai berikut a*b=c, cÎA, untuk sembarang a,bÎA. Operasi biner sering disebut komposisi biner.

Dengan kata lain, produk (dinotasikan dengan *) dari dua buah elemen sembarang di A akan menghasilkan elemen di A lagi (tertutup terhadap operasi *).

Contoh:

·        Penjumlahan dua buah bilangan bulat sembarang akan menghasilkan bilangan bulat lagi, sehingga penjumlahan adalah operasi biner pada himpunan bilangan bulat.

·        Perkalian dua buah bilangan riil sembarang akan menghasilkan bilangan riil lagi, sehingga perkalian adalah operasi biner pada himpunan bilangan riil.

OPERASI KOMUTATIF

Operasi * bersifat komutatif pada himpunan A, jika berlaku a*b = b*a, untuk setiap a,b Î A.

OPERASI ASOSIATIF

Operasi * bersifat asosiatif pada himpunan A, jika berlaku a*(b*c) = (a*b)*c, untuk setiap a,b,c Î A.

OPERASI DISTRIBUTIF

Operasi * bersifat distributif atas operasi Å pada himpunan A jika:

a*(bÅc) = (a*b) Å (a*c), untuk setiap a,b,c Î A (distributif kiri) dan

(a*b)Åc = (aÅc) * (bÅc), untuk setiap a,b,c Î A (distributif kanan)

HIMPUNAN-HIMPUNAN ISOMORFIS

          Himpunan S dan T isomorfis, jika:

1.   Ada korespondensi 1-1 antara S dan T

2.   Setiap relasi (operasi) pada S dan T tetap terpelihara dalam korespondensi tersebut.

Contoh:

S = {0, 1, 2, 3} dengan operasi tambah modulo 4, dan T = {1, 2, 3, 4} dengan operasi kali modulo 5 adalah isomorfis. Korespondensi 1-1 nya adalah 0®1, 1®3, 2®4, 3®2. Perlihatkan dengan tabel.

UNSUR KESATUAN KIRI ADITIF

Elemen eÎA yang bersifat  e + a = a untuk setiap aÎA, disebut unsur kesatuan kiri aditif. Contoh:

·        bilangan 0 pada operasi tambah bilangan bulat, 0+a=a

·        unsur air pada reaksi kimia, H₂O + HCl tidak bereaksi, hanya mengencerkan HCl

·        himpunan Æ pada operasi gabung “È”, yakni Æ È A = A

UNSUR KESATUAN KANAN ADITIF

Elemen eÎA yang bersifat  a + e = a untuk setiap aÎA, disebut unsur kesatuan kanan aditif. Contoh:

·        bilangan 0 pada operasi tambah bilangan bulat, a + 0 = a

·        unsur air pada reaksi kimia, HCl + H₂O tidak bereaksi, hanya mengencerkan HCl

·        himpunan Æ pada operasi gabung “È”, yakni  A È Æ  = A

UNSUR KESATUAN ADITIF

Elemen eÎA yang bersifat a + e = e + a = a, untuk setiap aÎA, disebut unsur kesatuan aditif. Contoh:

·        bilangan 0 pada operasi tambah bilangan bulat, 0+a=a+0=a

·        unsur air pada reaksi kimia, H₂O + HCl atau HCl + H₂O tidak bereaksi, hanya mengencerkan HCl

·        himpunan Æ pada operasi gabung “È”, yakni A È Æ  = Æ È A  = A

UNSUR KESATUAN KIRI MULTIPLIKATIF

          Elemen eÎA yang bersifat e * a = a, untuk setiap a ÎA,  disebut unsur kesatuan kiri multiplikatif. Contoh:

·        bilangan 1 pada operasi kali bilangan riil, yakni 1 * a = a

·        himpunan semesta pada operasi irisan “Ç”, yakni U Ç A = A

UNSUR KESATUAN KANAN MULTIPLIKATIF

          Elemen xÎA yang bersifat a * e = a, untuk setiap a ÎA,  disebut unsur kesatuan kanan multiplikatif. Contoh:

·        bilangan 1 pada operasi kali bilangan riil, yakni a*1=a

·        himpunan semesta pada operasi irisan “Ç”, yakni A Ç U = A

UNSUR KESATUAN MULTIPLIKATIF

          Elemen eÎA yang bersifat a * e = e * a = a, untuk setiap a ÎA,  disebut unsur kesatuan multiplikatif. Contoh:

·        bilangan 1 pada operasi kali bilangan riil, yakni 1*a = a*1 = a

·        himpunan semesta pada operasi irisan “Ç”, yakni U Ç A = A Ç U = A

INVERS ADITIF KIRI

          Elemen xÎA yang bersifat x + a = 0, untuk setiap aÎA, disebut invers aditif kiri dari a.

Contoh:

bilangan bulat –a adalah invers aditif kiri dari bilangan bulat a dengan operasi tambah, yakni –a + a = 0.

INVERS ADITIF KANAN

          Elemen xÎA yang bersifat a + x = 0, untuk setiap aÎA, disebut invers aditif kanan dari a.

Contoh:

bilangan bulat –a adalah invers aditif kanan dari bilangan bulat a dengan operasi tambah, yakni a + (-a) = 0.

INVERS ADITIF

          Elemen xÎA yang bersifat a + x = x + a = 0, untuk setiap aÎA, disebut invers aditif dari a.

Contoh:

bilangan bulat –a adalah invers aditif dari bilangan bulat a dengan operasi tambah, yakni a + (-a) = (-a) + a = 0.

INVERS MULTIPLIKATIF KIRI

          Elemen x yang bersifat x * a = 1, disebut invers multiplikatif kiri dari a.

Contoh:

Bilangan riil ¹/_a adalah invers multiplikatif kiri dari bilangan riil a¹0, yakni ¹/_a * a = 1.

INVERS MULTIPLIKATIF KANAN

          Elemen x yang bersifat a * x = 1, disebut invers multiplikatif kanan dari a.

Contoh:

Bilangan riil ¹/_a adalah invers multiplikatif kanan dari bilangan riil a¹0, yakni a * ¹/_a  = 1.

INVERS MULTIPLIKATIF

          Elemen x yang bersifat x * a = a * x = 1, disebut invers multiplikatif.

Contoh:

Bilangan riil ¹/_a adalah invers multiplikatif dari bilangan riil a¹0, yakni ¹/_a * a = a * ¹/_a = 1.

ARITMETIKA MODULAR

Definisi:

Bilangan bulat a ~ b, yakni a kongruen dengan b modulo m, jika mï(a-b), atau dengan simbol: aºb (mod m).

Buktikan bahwa relasi kongruen modulo m adalah relasi ekuivalen.

Aplikasi Kongurensi

1.   Bilangan acak semu (Pseudorandom Number)

Formula: x_n+1 = (a.x_n + c) (mod m).

Adapun a = pengganda (multiplier), c=pertambahan nilai (increment), dan x₀ = seed.

2£a<m, 0£c<m, 0£x₀<m.

Contoh:

Carilah bilangan-bilangan acak untuk m=9, a=7, c=4 dan x₀=3. Perhatikan bilamana terjadi perulangan?

Kebanyakan komputer menggunakan c=0 (pure multiplicative generator), m = 2³¹-1 dan a = 7⁵ = 16807. Akibatnya, 2³¹-2 bilangan dihasilkan sebelum terjadi perulangan.

2.   Kriptologi (cryptology)

Cipher Julius Caesar: (p+3) mod 26.

A	B	C	D	E	F	G	H	I	J	K	L	M
0	1	2	3	4	5	6	7	8	9	10	11	12

N	O	P	Q	R	S	T	U	V	W	X	Y	Z
13	14	15	16	17	18	19	20	21	22	23	24	25

Enkripsikan “MEET YOU IN THE PARK”, kemudian dekripsikan kembali.

3. Teorema Sisa Cina (Chinese Remainder TheoremI)

Definisi:

·        a.xºb (mod m) disebut kongruensi linier. Variabel x akan dicari, sedangkan a dan b adalah bilangan-bilangan bulat.

·        Jika ada bilangan bulat a’ sedemikian rupa sehingga a’.aº1 (mod m), maka a’ disebut invers dari a.

Teorema:

Jika a dan m bilangan-bilangan bulat yang relatif prima, dan m>1, maka invers dari a (mod m) ada.

Contoh:

·        Carilah invers dari 3 (mod 7)

·        Carilah solusi dari 3xº4 (mod 7)

Bilangan-bilangan bulat positif m₁, m₂, m₃, …, m_n adalah relatif prima sepasang-sepasang, artinya FPB (m_i,m_k) = 1, untuk sembarang i dan k, i¹k.

Sistem Persamaan Modulo:

x º a₁ (mod m₁)

x º a₂ (mod m₂)

x º a₃ (mod m₃)

…..

x º a_n (mod m_n)

Sistem persamaan tersebut mempunyai solusi unique modulo m=m₁.m₂.m₃….m_n. Ada solusi x dengan 0£x<m, dan semua solusi lain adalah kongruen modulo m dengan solusi ini.

M_k =(m/m_k), y_k = invers dari M_k, (mod m)

Contoh:

Sun-Tsu menyampaikan suatu problem: “suatu bilangan, bila dibagi dengan 3, akan bersisa 2, dan bila dibagi dengan 5 akan bersisa 3 dan bila dibagi dengan 7 akan bersisa 2. Bilangan manakah itu?