teori bilangan

Bab I Keterbagian

BAB IKETERBAGIAN

A. Sifat-Sifat Keterbagian

Sifat-sifat keterbagian merupakan dasar pengembangan teori bilangan, sehingga

sifat-sifat ini banyak digunakan dalam uraian-uraian selanjutnya. Sifat keterbagian ini

juga merupakan titik pangkal dalam pembahasan kekongruenan.

Jika suatu bilangan bulat dibagi oleh bilangan bulat lain yang bukan nol, maka

hasil baginya adalah bilangan bulat atau bukan bilangan bulat.

Definisi 1.1:

a | b dibaca a membagi b atau b habis dibagi a dengan a 0 jika dan hanya

jika ada suatu bilangan bilangan bulat x sehingga b = ax.

Contoh:

1. 3|15 sebab ada bilangan bulat 5, sehingga 15 = 3.5

2. 4|28 sebab ada bilangan bulat 7, sehingga 28 = 4.7

3. -2|-16 sebab ada bilangan bulat 8, sehingga -16 = -2.8

4. 3∤17 sebab tidak ada bilangan bulat x, sehingga 17 = 3.x

Berdasarkan definisi 1.1, pembagian di dalam (himpunan bilangan bulat) dapat

dilakukan tanpa memperluas menjadi (himpunan bilangan rasional), yaitu dengan

menggunakan sifat:

Jika a, b dan a.b 0, maka a 0 atau b 0.

Sifat ini memungkinkan dilakukan penghapusan faktor, misalnya:

Jika a, b dan 8a=8b, maka 8a – 8b 0, 8(a - b) 0 atau a b.

Jadi, persamaan 8a 8b, menjadi a b tidak diperoleh dari mengalikan ruas kiri dan

ruas kanan dengan bukan bilangan bulat .

Teori Bilangan 1

Bab I Keterbagian

Selanjutnya, pernyataan a|b sudah mempunyai makna a 0, meskipun a 0 tidak

ditulis.

Beberapa sifat dasar adalah:

1. 1|a untuk setiap a karena ada a , sehingga a l.a

2. a|a untuk setiap a dan a 0, karena ada 1 sehingga a a.1

3. a|0 untuk setiap a dan a 0, karena ada 0 sehingga 0 a.0

4. a|b, a 0, maka kemungkinan hubungan antara a dan b adalah a b, a b, atau a b

Teorema 1.1:

Jika a, b dan a|b, maka a|bc, untuk setiap c .

Bukti:

Diketahui a|b, maka sesuai definisi 1.1, ada suatu x sehingga b ax. Jika

kedua ruas, ruas kiri dan kanan dikali dengan c maka bc (ax)c atau bc a(cx)

untuk setiap c . Ini berarti ada y cx , sehingga bc ay. Jadi, a|bc.

Teorema 1.2:

Jika a,b,c , a|b dan b|c, maka a|c.

Contoh:

Jika 4|8 dan 8|16 maka 4|16

Teorema 1.3:

Jika a,b , a|b dan b|a, maka a b atau a -b

Bukti:

Diketahui a|b dan b|a, maka sesuai definisi 1.1, ada x,y sehingga b ax dan

a by. Ini berarti a (ax)y atau a a(xy), sehingga diperoleh a - a(xy) 0 atau

a(1 - xy) 0.

Karena a 0 dan a(1 - xy) 0 maka 1 - xy 0, atau xy = 1.

Karena x,y dan xy = 1, maka x = y = 1, atau x = y = -1.

Jika x = y = 1, maka a = b, dan jika x = y = -1, maka a = -b. Jadi, a = b atau a = -b

Teori Bilangan 2

Bab I Keterbagian

Teorema 1.4:

Jika a,b , a|b dan a|c, maka a|(b + c) atau a|(b – c)

Bukti:

Akan dibuktikan a|(b+c).

Diketahui, a|b dan a|c, maka sesuai definisi 1.1, ada x,y sehingga b ax dan

c ay. Jika kedua persamaan di atas dijumlahkan, diperoleh b + c = a(x + y).

Karena x,y , maka sesuai sifat ketertutupan operasi penjumlahan (x + y) .

Dengan demikian, ada (x + y) sehingga b + c = a(x + y). Jadi, a|(b + c).

Dengan cara yang sama dapat dibuktikan a|(b – c).

Teorema 1.5:

Jika a,b,c , a|b dan a|c, maka a|(bx + cy) untuk semua x,y

Contoh:

4|8 dan 4|12, maka 4|(8.2 + 12.3) = 4|52

Teorema 1.6:

Jika a,b,c , a > 0, b > 0, dan a|b, maka a b.

Bukti:

Diketahui a|b, maka menurut definisi 1.1, ada x sehingga b ax. Karena

a > 0, b > 0, maka x > 0. Karena x dan x > 0, maka kemungkinan nilai-nilai x

adalah x = 1 atau x > 1. Jika x = 1 atau x > 1 dan b = ax, maka b = a atau b > a.

Jadi, a b.

Teori Bilangan 3

Bab I Keterbagian

Berikut, pengertian keterbagian dikaitkan dengan harga mutlak. Perlu diketahui

definisi dan sifat-sifat nilai mutlak sebagai berikut,

.

Definisi 1.2 (Nilai Mutlak):

Sifat-Sifat:

1.

2.

3.

Teorema 1.7:

Jika a|b dan b 0, maka

Contoh:

1. a = 6, b = 12, 6|12, maka

2. a = -6, b = 12, -6|12, maka

3. a = 6, b = -12, 6|12, maka

4. a = -6, b = -12, -6|-12, maka

Teorema 1.8:

Jika ditentukan barisan bilangan (0, 1, 2, 3, …, (|a| - 1)) dengan a 0

maka beda dua bilangan sebarang dari barisan itu tidak terbagi oleh a,

kecuali beda dua bilangan sebarang itu sama dengan nol.

B. Algoritma Pembagian Bilangan Bulat

Algoritma pembagian merupakan langkah sistematis untuk melaksanakan

pembagian sehingga diperoleh hasil pembagian dan sisa pembagian yang memenuhi

hubungan tertentu.

Teori Bilangan 4

Bab I Keterbagian

Peragaan berikut tentang hubungan antara bilangan bulat a dan b, dengan a > 0

dan b dinyatakan dalam a.

b a b = qa + r

27

46

-103

5

8

11

27 = 5.5 + 2

46 = 5.8 + 6

-103 = (-10)11 + 7

Keadaan di atas rnenunjukkan bahwa jika a,b dan a > 0, maka ada q,r

sehingga b = qa + r dengan . Fakta ini menunjukkan penerapan dalil Algoritrna

Pembagian.

Dalil Algoritma Pemhagian

Jika a,b dan a > 0, maka ada bilangan bulat q dan r yang masing-masing

tunggal sehingga b = qa + r dengan .

Dari Dalil Algoritrna Pembagian di atas, jika a|b, maka b = qa + 0, berarti r = 0.

Dan jika a∤b, maka r 0, yaitu 0 < r < a.

Untuk memudahkan alur dari pembuktian dalil di atas, simaklah dengan cermat

uraian berikut.

Diketahui dua bilangan bulat 4 dan 7 dengan jika 4∤7 maka dapat dibuat suatu

barisan aritmetika (7 - 4n) dengan n yaitu:

n : -1 0 1 2 3 4 … n

Barisan : 11, 7, 3, -1, -5, -9, …, (7 – 4n)

Barisan bilangan di atas mempunyai suku-suku yang negatif dan non negatif.

Misalkan S adalah himpunan bilangan suku-suku barisan yang non negatif, yaitu

S = {3, 7, 11, ... } atau S = {7 – 4n | n , (7 – 4n) 0}

Karena S N dan N adalah himpunan terurut rapi (Well Ordered Set), S mempunyai

unsur terkecil, yaitu 3. 3 S, maka 3 dapat dinyatakan sebagai (7 – 4n) dengan n = 1,

yaitu 3 = (7 – 4.1), sehingga

Teori Bilangan 5

Bab I Keterbagian

7 = 1.4 + 3 dengan 0 < 3 < 4

7 = q.4 + r dengan q = 1, r = 3 dan

Jadi, dari 4, 7 ada q,r sehingga 7 = q.4 + r dengan .

Bukti (Dalil Algoritma Pembagian):

1. Menunjukkan eksistensi hubungan b = qa + r

Karena a,b maka dapat dibentuk suatu barisan aritmetika (b – na) dengan n ,

yaitu: …, b – 3a, b – 2a, b – a, b, b + a, b + 2a, b + 3a, ....

Misalkan S adalah himpunan bilangan suku-suku barisan yang tidak negatif, yaitu

S = {b – na | n , (b – na) 0}

Maka menurut prinsip urutan rapi, S mempunyai unsur terkecil r. Karena r , maka

r dapat dinyatakan sebagai r = b – qa dengan q , berarti b = qa + r.

2. Menunjukkan

Anggaplah tidak benar bahwa , maka r a. (r tidak mungkin negatif karena

r ). Karena r a rnaka r – a 0

Karena r = b – qa, maka r – a = b – (q + 1)a

r – a 0 dan r – a mempunyai bentuk (b – na) maka (r – a) . Diketahui a > 0,

maka r – a < r, sehingga (r – a) merupakan unsur S yang lebih kecil dari r. Hal ini

kontradiksi dengan r sebagai unsur terkecil S.

Jadi, .

3. Menunjukkan ketunggalan q dan r.

Misalkan q dan r tidak tunggal, ada q1, q2, r1, r2 dengan q1 q2, dan r1 r2 yang

memenuhi hubungan :

b = q1a + r1,

b = q2a + r2,

Dengan demikian dapat ditentukan bahwa:

q1a + r1 = q2a + r2 atau r1 - r2 = a(q2 – q1) sehingga a | (r1 - r2)*

Untuk r1 r2, misal r1 > r2, maka dari dan diperoleh (r1 - r2) < a

dan (r1 - r2) > -a. Sehingga -a < (r1 - r2) < a. Bentuk ini dapat dipisahkan menjadi 0

< (r1 - r2) < a, dan –a < ( r1 - r2) < 0.

Teori Bilangan 6

Bab I Keterbagian

a. 0 < (r1 - r2) < a, berarti a > (r1 - r2)

a > 0, (r1 - r2) > 0 dan a > (r1 - r2), maka a ∤ (r1 - r2) kontradiksi dengan a

| (r1 - r2)*

b. -a < (r1 - r2) < 0, berarti 0 < (r2 – r1) < a

a > 0, (r2 – r1) > 0 dan a > (r2 – r1), maka a ∤ (r2 – r1) kontradiksi dengan

a | (r1 - r2)*

Jadi, q1 = q2 dan r1 = r2 atau q dan r tunggal.

Definisi 1.3:

Jika a,b,q,r , b = qa + r dengan , maka b disebut bilangan yang

dibagi (divident), a disebut bilangan pembagi (divisor), q disebut bilangan

hasil bagi (quotient) dan r disebut bilangan sisa pembagian (remainder).

Dalil Algoritma Pembagian menjamin eksistensi dari bilangan hasil bagi dan sisa

pembagian dari pembagian dua bilangan bulat.

Jika b sebarang bilangan bulat dan a = 2, maka menurut dalil pembagian:

b = 2q + r dengan .

Karena , maka r = 0 atau r = 1

Untuk r = 0, b = 2q + 0 = 2q. Dan b = 2q disebut bilangan bulat genap (even integer).

Untuk r = 1, b = 2q + 1. Dan b = 2q + 1 disebut bilangan bulat ganjil (odd integer).

Dengan demikian, setiap bilangan bulat merupakan bilangan bulat genap dan bilangan

bulat ganjil.

Contoh:

Misal a = 45, b = 20

Dengan menggunakan algoritma pembagian

Ada 2, 5 sehingga 45 = 20.2 + 5

Dengan 0 < 5 < 20

Teori Bilangan 7

Bab II Faktor Persekutuan TerbesarFaktor Persekutuan

BAB IIFAKTOR PERSEKUTUAN TERBESAR

(FPB)

Jika A adalah himpunan semua faktor a = 8, B adalah himpunan semua faktor b = 12

dan C adalah himpunan faktor persekutuan dari a dan b, maka:

A = {-8, -4, -2, -1, 1, 2, 4, 8}

B = {-12, -6, -4, -3, -2, -1, 1, 2, 3, 4, 6, 12}

C = A B = {-4,-2,-1, 1, 2, 4}

Semua faktor persekutuan dari himpunan A dan himpunan B adalah semua anggota

himpunan A B, dan membagi habis bilangan bulat a dan b.

Definisi 2.1:

Suatu bilangan bulat d adalah faktor persekutuan a dan b dengan a, b , a

dan b keduanya tidak nol jika dan hanya jika d|a dan d|b.

Contoh di atas menunjukkan bahwa 4 adalah faktor persekutuan dari 8 dan 12 karena

4|8 dan 4|12. Demikian pula 2 adalah faktor persekutuan dari 8 dan 12 karena 2|8 dan 2|12.

Perhatikan contoh di atas, C adalah himpunan semua faktor persekutuan dari a dan b,

serta 4 merupakan bilangan bulat positif terbesar dari unsur C. Dengan demikian, 4 adalah

faktor persekutuan terbesar dari 8 dan 12, yaitu 4 merupakan bilangan bulat positif terbesar

yang membagi 8 dan 12. Dengan cara yang sama dapat ditunjukkan bahwa 4 merupakan

bilangan bulat positif terbesar yang membagi -8 dan -12 atau -8 dan 12 atau 8 dan -12. Jika

faktor persekutuan a dan b dilambangkan dengan (a,b), maka (8,12)= (-8, -12) = (-8, 12) = (8,

-12) = 4.

Definisi 2.2:

Misalkan a,b , a dan b keduanya tidak nol, dan d adalah faktor persekutuan

terbesar dari a dan b jika dan hanya jika d faktor persekutuan dari a dan b. Jika

c faktor persekutuan dari a dan b, maka c d.

Teori Bilangan 9


Berdasarkan definisi 2.1 dan 2.2, maka diperoleh pernyataan sebagai berikut.

d = (a,b) jika dan hanya jika (i) d|a dan d|b

(ii) Jika c|a dan c|b, maka c d

Contoh:

Carilah faktor persekutuan dan faktor persekutuan terbesar dari 16 dan 24 .

Jawab:

A adalah himpunan semua faktor 16.

A = { -16, -8, -4, -2, -1, 1, 2, 4, 8, 16}

B adalah himpunan semua faktor 24.

B = {-24, -12, -8, -6, -4, -3, -2, -1, 1, 2, 3, 4, 6, 8, 12, 24}

C = A B = {-8,-4,-2,-1, 1, 2, 4, 8}

Teorema 2.1:

Jika a,b dan d = (a, b), maka ( ) = 1

Bukti:

Misalkan (a/d, b/d) = c. Akan ditunjukkan bahwa c = 1

Akan diperlihatkan c 1 dan c 1.

Karena c faktor persekutuan terbesar dari bilangan bulat a dan b, maka c 1.

Selanjutnya, akan ditunjukkan c 1.

(a/d, b/d) = c berdasarkan definisi 2.1 maka c|(a/d) dan c|(b/d)

Jika c|(a/d), maka q a/d = cq, menurut definisi pembagian a = (cq)d = (cd)q

Jika c|(b/d), maka q b/d = cr, menurut definisi pembagian b = ( cr)d = (cd)r

Dengan demikian, (cd) faktor persekutuan a dan b. Karena d faktor persekutuan

terbesar dari a dan b maka cd d (berdasarkan definisi 2.2), karena d positif maka

c 1.

Dengan demikian, c 1 dan c 1. Jadi, c = 1.

Contoh:

Misal a = 30 dan b = 35

Teori Bilangan 10


(a, b) = (30, 45) = 5

( ) = (6, 7) = 1

Teorema 2.2:

Jika b = qa + r, maka (b,a) = (a,r)

Untuk pembuktian, gunakan Algoritma Pembagian Bilangan bulat.

Contoh:

Misal a = 35, b = 60

Dengan menggunakan algoritma pembagian

60 = 35.1 + 25

(35, 25) = 5 berarti (60, 35) = 5

Teorema 2.3:

Jika d = (a, b), maka d adalah bilangan bulat positif terkecil yang mempunyai

bentuk ax + by dengan x,y .

Bukti:

Nilai-nilai ax + by dengan x,y disusun dalam suatu barisan.

Misalkan S adalah himpunan bilangan unsur-unsur barisan yang positif, yaitu:

S = {ax + by > 0 dan x,y }

Maka S N.

Karena N merupakan himpunan terurut rapi dan S N, maka S mempunyai unsur

terkecil, misal t.

t S maka x,y sehingga t = ax + by. Jadi, t adalah bilangan bulat positif terkecil

yang berbentuk ax + by. Selanjutnya, akan ditunjukkan bahwa t = d = (a, b). Pertama,

akan ditunjukkan t|a dan t|b.

Andaikan t ∤ a, Maka a qt untuk semua q . Menurut algoritma pembagian

a = qt + r dengan 0 < r < t sehingga:

r = a – qt = a – q(ax + by) = a(1 – qx) + b(-qy)

Dengan demikian, r S karena r mempunyai bentuk umum unsur S.

Teori Bilangan 11


Karena r,t S dan r < t, maka r adalah unsur terkecil dari S. Hal ini kontradiksi karena

t unsur terkecil dari S. Jadi, haruslah t|a.

Dengan cara yang sama, dapat ditunjukkan untuk t|b.

Jadi, berlaku t|a dan t|b.

Kedua, akan ditunjukkan bahwa t = d = (a, b)

d = (a, b), maka sesuai definisi 2.1, d|a dan d|b. Berdasarkan definisi 1.1,

m,n sehingga a = md dan b = nd.

Dari t = ax + by, menjadi t = (md)x + (nd)y atau t = d(mx + ny), berarti d|t karena (mx

+ ny) . Karena d|t, t > 0 dan d > 0, maka berdasarkan teorema 1.6, d t.

Karena t faktor persekutuan dari a dan b, dan d = (a, b) maka t d.

Karena d t dan t d maka t = d.

Jadi, t = d = (a, b) merupakan bilangan bulat positif terkecil yang berbentuk ax + by

dengan x,y .

Teorema 2.4:

Jika m dan m > 0, maka (ma, bm) = m(a, b).

Bukti:

(a, b) = d, berdasarkan definisi 2.1, maka d|a dan d|b

Sehingga md|ma dan md|mb

(ma, mb) = md

(ma, mb) = m(a, b)

Contoh:

(40, 50) = 10

(40, 50) = (10. 4, 10. 5) = 10(4, 5), di mana (4, 5) = 1

Teorema 2.5:

Teori Bilangan 12


Jika (a, m) = 1 dan (b, m) = 1, maka (ab, m) = 1

Bukti:

(a, m) = 1, sehingga ax + my = 1, ax = 1 – my untuk setiap x,y

(b, m) = 1, sehingga br + ms = 1, br = 1 – ms untuk setiap r,s

(ax)(br) = (1 – my)(1 – ms)

(ab)(xr) = 1 – ms – my + m2sy = 1 – m(s + y – msy)

q = (xr) dan p = (s + y – msy), sehingga

(ab)q = 1 – mp

(ab)q + mp = 1

(ab, m) = 1

Teorema 2.6:

Jika a,b,c , a|bc, dan (a, b) = 1, maka a|c

Bukti:

(a, b) = 1, maka sesuai Teorema 2.3, ada bilangan bulat positif yang mempunyai

bentuk ax + by, dengan x,y , yaitu ax + by = 1.

ax + by = 1, maka c(ax) + c(by) = c atau a(cx) + b(cy) = c.

a|bc, maka menurut Teorema 1.1 a|(bc)y untuk setiap y

a|acx karena acx mempunyai faktor a

Karena a|bcy dan a|acx maka menurut Teorema 1.5, a|(acx + bcy)

Karena a|(acx + bcy) dan a(cx) + b(cy) = c, maka a|c.

Teorema 2.7:

Misalkan a,b , d = (a, b) jika dan hanya jika d > 0, d|a dan d|b, untuk

setiap f faktor persekutuan dari a dan b.

Bukti:

Misal d = (a, b), sehingga d|a dan d|b.

Sesuai dengan Teorema 2.3, d = ax + by untuk setiap x,y . Dengan ini, jika f |a dan

f |b, maka f |(ax + by), sehingga f |d.

Sebaliknya, misalkan d|a dan d|b, untuk setiap d . Diberikan f |a dan f |b, sehingga

f |d. Mengakibatkan d f, sehingga d = (a, b).

Teori Bilangan 13


Contoh:

Faktor 20 = {-20, -10,-5, -4, -2, -1, 1, 2, 4, 5, 10, 20}

Faktor 35 = {-35, -7, -5, -1, 1, 5, 7, 35}

Faktor persekutuan 20 dan 35 adalah {-5, -1, 1, 5}

Faktor persekutuan terbesar 20 dan 35 atau (20, 35) = 5

Jadi, -5| 5; -1|1; 1|5; dan 5|5

Teorema 2.8 (Dalil Algoritma Euclides):

Jika r0, r1 , r0 > r1 dan r0, r1 > 0, maka

r0 = q1r1 + r2

r1 = q2r2 + r3

r2 = q3r3 + r4

.

.

.

rk-2 = qk-1rk-1 + rk

rk-1 = qkrk + rk+1

rk = qk+1r k+1 + rk+2

0 r2 < r1

0 r3 < r2

0 r4 < r3

.

.

.

0 rk < rk-1

rk+1 0 dan (r0, r1) = rk

Teori Bilangan 14

teori bilangan

Documents