KETERBAGIAN

Posted: 14 April 2010 in Teori Bilangan
Tag:

Keterbagian Dalam Bilangan Bulat

Sifat-sifat yang berkaitan dengan keterbagian telah dipelajari oleh Euclid 350 SM (Niven, 1999:4).  Pengembangan selanjutnya telah banyak dikembangkan oleh beberapa ahli matematika yang lain, misalnya yang berkaitan dengan bilangan komposit, perkalian dalam usaha untuk mengembangkan teori bilangan. Karena pentingnya sifat keterbagian maka akibatnya konsep tersebut sering muncul dalam Aljabar Modern dan Struktur Aljabar (Muhsetyo, 1994:18)

Definisi

Suatu bilangan bulat x dikatakan habis dibagi oleh suatu bilangan bulat y ≠ 0, jika terdapat satu bilangan bulat p sedemikian sehingga x = py. Jika hal ini dipenuhi maka y dikatakan membagi x dan dinotasikan dengan y x yang dapat diartikan sebagai y adalah faktor (pembagi) x, atau x adalah kelipatan y. Jika y tidak membagi x dinotasikan dengan y x.

Contoh :

1)     3 │12, sebab ada bilangan bulat 4 sedemikian sehingga 12 = (4) 3.

2)     3 │-30, sebab ada bilangan bulat -10 sedemikian sehingga

–30 = (-10)3.

Dalil

Jika a,b,c   Z maka berlaku:

1)     a│ b →  a │bc,  untuk setiap c   Z.

2)     (a │ b, b │c) → a │ c.

3)     (a │ b, b │a) → a = ± b.

4)     (a │ b, a │c) → a │ (b ± c).

5)     (a │ b, a │c) → a │ (ax + by) untuk setiap  x,y   Z.

Untuk selanjutnya ax + by disebut kombinasi linear dari b dan c

6)     ( a>0, b > 0 dan a │b) → a ≤ b.

7)     a │b ↔ ma │ mb untuk setiap m  Z dan m ≠ 0

8) ( ab dan a b+c ) a c.

Nenymoo

(Dalil Algoritma Pembagian)

Jika a > 0, dan a,b  Z, maka ada bilangan-bilangan q, r  Z yang masing-masing tunggal (unique)  sehingga b = qa + r dengan  0 ≤ r < a.

Jika a ┼ b maka r memenuhi ketidaksamaan 0 < r < a.

Bukti.

Misal a, b  Z, maka dapat dibentuk suatu barisan aritmatika b – na, n  Z, yaitu:

…, b –3a, b – 2a, b-a, b, b + a, b + 2a, ….

Barisan di atas mempunyai bentuk umum b – na.

Selanjutnya, misal S adalah suatu himpunan yang unsur-unsurnya suku yang bernilai positip dari barisan b – na, sehingga:

S = { (b – na) │n  Z, dan b – na > 0 }

Menurut prinsip urutan, maka S mempunyai unsur terkecil, sebut saja r.

Karena r  S, maka r dapat dinyatakan sebagai r = b – qa, dengan q  Z.

Dari r = b – qa dapat diperoleh b = qa + r.

Jadi jika a > 0 dan a,b  Z maka ada q,r  Z  sedemikian sehingga b = qa + r.

Untuk menunjukkan bahwa  0  r < a, maka digunakan bukti tidak langsung sebagai berikut:

Anggaplah bahwa 0  r < a tidakbenar, maka r  a dan dalam hal ini r tidak mungkin negatip karena r  S.

Jika r  a maka r – a  0.

r = b – qa  r – a = b – qa – a

= b – ( q +1) a.

r – a  0 dan  r-a = b – ( q + 1 ) a   0.

r – a  0 dan r – a mempunyai bentuk b – na, maka r – a  S.

Karena a > 0 maka r – a < r sehingga r – a merupakan unsur terkecil dari S dan lebih kecil dari r. Hal ini bertentangan dengan pengambilan r sebagai unsur terkecil S. Jadi haruslah 0  r < a.

Untuk menunjukkan ketunggal q dan r, dimisalkan q dan r tidak tunggal yaitu q1, q2, r1, r2 Z dan memenuhi hunbungan persamaan

b = q1a +  r1

b = q2a +  r2

Sehingga   berlaku  q1a+ r1 = q2a+ r2

( q1 – q2 ) a + ( r1 – r2 ) = 0

( r1 – r2 ) = ( q2 – q1 )a

a │          ( r1 – r2 )

a │          ( r1 – r2 )  r1 – r2 = 0 atau  r1 – r2 a ( a  r1 – r2 )

r1 – r2 = 0  r1 = r2 (q1 – q2 ) a  = 0  q1 =  q2

r1 – r2 a > 0, r1 > 0 , r2 > 0  r1 a = 0.

Jadi r1 =  r2 dan q1 = q2 yaitu q dan r masing-masing adalah tunggal.

Selanjutnya jika a ┼ b, maka tidak ada q  Z sehingga b = qa. Hal ini berarti b qa atau b = qa + r dengan  0 < r < a. ( r 0, sebab jika r = 0 diperoleh b = qa).

Definisi

Ditentukan x,y Z yang keduanya tidak bersama-sama bernilai 0, a Z disebut pembagi persekutuan dari x dan y jika a x dan a y.

a  Z disebut pembagi persekutuan terbesar (FPB) dari x dan y jika a adalah bilangan bulat positip terbesar sehingga a│x dan a│y.

Untuk selanjutnya jika a adalah pembagi persekutuan terbesar dari x dan y dinyatakan dengan (x,y) = a.

Perlu diperhatikan bahwa (x,y) = a didefinisikan untuk setiap pasangan bilangan bulat x,y  Z kecuali untuk x = 0 dan y = 0. Demikian pula perlu dipahami bahwa (x,y) selalu bernilai positip yaitu (x,y) > 0, atau (x,y) ≥ 1.

Contoh:

  1. Faktor dari 8 adalah  -8, -4, -2, -1, 1, 2, 4, 8.
  2. Faktor dari 20 adalah –20, -10, -5, -4, -2, -1, 1, 2, 4, 5, 10, 20
  3. Faktor Persekutuan 8 dan 20 adalah –4,-2,-1, 1, 2, 4
  4. Faktor Persekutuan terbesar 8 dan 20 adalah 4 atau (8,20) = 4

Selanjutnya perhatikan bahwa

(12,16) = 4,  (60,105) = 15, (3,5) = 1, (17,19)= 1. dan seterusnya.

Dalil

  1. Jika d = (x,y) maka d adalah bilangan bulat positip terkecil yang mempunyai bentuk umum  aox + boy dengan ao, bo Z

Bukti.

Dibentuk kombinasi linear (ax + by)  dengan a,b  Z. Barisan bilangan ax + by memuat bilangan-bilangan negatip, bilangan nol (untuk a = 0 dan b = 0), dan bilangan-bilangan yang bernilai positip.

Ambil S = {ax + by │ ax + by > 0 }, maka dapat ditentukan bahwa S  N. Karena N adalah himpunan terurut dan S  N, maka S mempunyai unsur terkecil dan sebutlah dengan t, dan t S, maka tentu ada a = ao dan b = bo sehingga  t = aox + boy dan selanjutnya dapat dibuktikan bahwa  t │ x  dan t │ y.

Untuk membuktikan apakah t │ x, digunakan bukti tidak langsung .

Misal  t ┼ x, maka menurut dalil sebelumnya ada q,  r Z sehingga

x = qt + r dengan 0 < r < t

r = x – qt

= x – q(aox + boy)

r = ( 1-aoq)x + (-boq)y

r =  a1x + b1y dengan  a1 = 1-aoq  Z, dan

b1 = -boq   Z.

Jadi r = a1x + b1y  Z dengan r, t S, t merupakan unsur terkecil  S ran r < t. Hal ini bertentangan dengan dengan pemisalan  t ┼ x. Dengan demikian anggapan t ┼ x tidaklah benar. Jadi haruslah t │ x.

Dengan cara yang sama dapat ditunjukkan bahwa t │ y.

Dari t │ x dan t │ y berarti t adalah pembagi persekutuan dari x dan y.

d = (x,y) berarti d │ x sehingga  p  S sehingga x = dp.

d = (x,y) berarti d │ y sehingga  p  S sehingga y = dp.

t = aox + boy

= ao (dp) + bo (dp)

d │ t,  d 0, t > 0 maka sesuai dengan dalil sebelumnya d  t dan d tidak lebih kecil dari t, sedangkan d adalah pembagi persekutuan dari x dan y.

Jadi d = t = aox + boy

Berdasarkan urian di atas jelaslah bahwa d = (x,y) merupakan bilangan bulat positip terkecil yang mempunyai bentuk (ax + by) dengan a,b  Z.

Dengan demikian terlihat bahwa tidak ada bilangan positip selain d yang membagi x dan y dan mempunyai bentuk (ax + by)

  1. Jika t  Z dan t > 0, maka (tx,ty) = t (x,y)

Bukti

Sesuai dengan bukti dalil 1 di atas, maka:

(tx,ty) =  bilangan bulat positip terkecil yang mempunyai bentuk(atx + bty) dengan    bilangan a,b  Z

=  atx + bty

= t (ax + by)

= t merupakan bilangan bulat positip terkecil yang mempunyai bentuk (ax+by)

=  t (ax +by)

  1. Jika x,y  Z dan d = (x,y) maka (,) = 1

Bukti

d = (x,y) berarti d │x dan d │y dan ,   Z

(x,y) = (d. , d.) = d (, )

Karena d > 0 maka d (, ) atau 1 =  (, )

Dengan demikian (, ) = 1

  1. Jika x,y,w  Z,  w │xy, dan (y,w) = 1 maka w │ x.

Bukti

(y,w) = 1 maka menurut definisi FPB 1 adalah bilangan bulat positip terkecil  yang mempunyai bentuk ay + bw dengan a,b  Z

ay + bw = 1 berarti ayx + bwx = x

w │ xy → w │ axy

w │ axy dan w │ bxw → w │ axy + bxw

w │ axy + bwx dan axy + bxw = x  → w │ x.

  1. Jika (x,t) = 1 dan (y,t) = 1, maka (xy,t) = 1

Bukti:

(x,t) = 1 → terdapat ao dan bo Z sedemikian sehingga aox+bot=1

(y,t) = 1 → terdapat ao dan bo Z sedemikian sehingga a1y+b1t=1

aox+bot=1   → aox = 1 – bot

a1y+b1t=1   → a1y = 1 – b1t

a1x = 1 – bot   dan a1y = 1 – b1t  maka:

(aox)(a1y) = (1 – bot)(1 – b1t)

= 1- (bo – b1 + bob1t)t

(aoa1)(xy) = (1- b2)t atau  (xy) a2 +b2t=1 dengan

a2 = aoa1 dan b2 = bo – b1 + bob1t

Karena (xy,t) = 1 adalah bilangan bulat positip tekecil yang mempunyai bentuk (xy) a2 +b2t=1 maka (xy,t) haruslah 1 sehingga (xy,t) = 1

  1. Ditentukan x,yZ , (x,y) = d. Ekuivalen dengan d > 0, d │x,   d│y dan f │d untuk setiap f pembagi persekutuan x dan y.

Bukti

d = (x,y) maka menurut definisi d adalah bilangan bulat positip terbesar  sehingga d │x,      d│y, hal ini berarti bahwa d > 0. Demikian pula d = (x,y) berarti d adalah bilangan bulat positip terkecil dan berbentuk (ax + by), dengan a,bZ.

Jadi d = ax + by.

Misal f adalah sebarang pembagi persekutuan dari x dan y, maka berlaku f │x dan f │y, sehingga f  │ax dan f │ay dan menurut sifat keterbagian berlaku f │ ax + by.

f │ ax + by  dan d = ax + by → f │d.

Sebaliknya, jika d > 0 dan d │ x   d│ y serta f │ d, dengan f adalah sebarang pembagi persekutuan x dan y maka d  f ( karena d = kf, k Z ) untuk sebarang f pembagi persekutuan x dan y.

Jadi d adalah pembagi persekutuan terbesar  dari x dan y. Atau d = (x,y)

  1. Untuk setiap a, x, y  Z, berlaku:

( x,y ) = ( y,x ) = ( x,-y) = ( x, y + ax ).

Bukti

d = (x,y) maka menurut definisi d adalah bilangan bulat positip terbesar  sehingga d │x,      d│y, hal ini berarti bahwa d > 0.

Jadi d = (x,y) atau d = (y,x).

Karena d merupakan bilangan bulat positip terbesar yang membagi x dan y, dan y membagi (-y), maka d juga merupakan bilangan bulat positip terbesar yang membagi x dan (-y), sehingga d = (x,-y).

Selanjutnya (x,y) │x berarti (x,y) │ax.

(x,y) │ax  dan (x,y) │y → (x,y) │ax + y.

(x,y) │ax dan (x,y) │ax + y →(x,y) adalah pembagi persekutuan dari x dan y+ax, sehinggga menurut dalil sebelumnya berarti (x,y) │(x,y+ax)

(x,y+ax) adalah pembagi persekutuan dari x dan (y+ax), hal ini berarti

(x,y+ax) │x  dan (x,y+ax) │ (y+ax)

(x,y+ax) │x   (x,y+ax) │ax 

(x,y+ax) │x  dan (x,y+ax) │y+ax  (x,y+ax) │y

Karena (x,y+ax) adalah suatu pembagi persekutuan dari x dan y,

maka  (x,y+ax) │  (x,y) . Jadi (x,y+ax) = (x,y)

Cara Lain Menentukan Faktor Persekutuan Terbesar dan Kombinasi    Linear

Marilah kita ingat kembali dalil  Algoritma Pembagian Euclides

Jika r1, r2 Z, dan r1 > r2 dan dengan proses algoritma pembagian dibentuk

Suatu barisan menurun bilangan-bilangan bulat r1, r2, r3, … , rk-1, rk, rk+1=0

Yaitu:

r1 =  q1r2 + r3 ,    0 ≤ r3 < r2.

r2 =  q2r3 + r4 ,    0 ≤ r4 < r2.

r3 =  q3r4 + r5 ,    0 ≤ r5 < r2.

r4 =  q4r5 + r6 ,    0 ≤ r6 < r2.

………………………………………

rk-2 =  qk-2rk-1 + rk ,    0 ≤ rk < r2.

rk-1 =  qk-1rk + rk+1 ,    rk+1 = 0

Maka (r1,r2) = rk.

Sehingga diperoleh :

r3 =  r1 – q1r2

r4 =  r2 – q2r3

r5 =  r3 – q3r4

r6 =  r4 – q4r5

ri =  ri-2 – qi-2ri-1

Berdasarkan persamaan tersebut di atas dapat diketahui bahwa bilangan bulat ri ditentukan oleh r1-1 dan ri-2

Andaikata Algoritma pembagian Euclid di atas dinyatakan dalam bentuk x dan y, yaitu:

x1 =  q1x2 + x3 ,    0 ≤ x3 < x2.

y1 =  q1y2 + y3 ,    0 ≤ y3 < y2.

maka dengan cara yang sama (analog) diperoleh bentuk persamaan dalam x dan y yang secara umum dinyatakan oleh xi =  xi-2 – qi-2xi-1 dan yi =  yi-2 – qi-2yi-1 .

Sehingga terdapat 3 persamaan dalam bentuk ri, xi, dan yi dan selanjutnya masing-masing konstanta tersebut  dapat dimulai dengan syarat awal yang berbeda.

r-1 = r1,   ro = r2

x-1 = 1,   xo = 0

y-1 = 0,   ro = 1

Secara lengkap langkah untuk menentukan masing-masing konstanta dapat dilihat pada table berikut ini:

i qi+1 ri xi yi
-1 * r1 (b) 1 0
0 r2 (a) 0 1
1 ….. …. …..
2 ….. ….. …. …..
3 ….. ….. …. …..
Dstnya. ….. ….. …. …..

Titik-titik pada masing-masing kolom diisi dengan menyesuaikan bentuk persamaan

ri =  ri-2 – qi-2ri-1

xi =  xi-2 – qi-2xi-1

yi =  yi-2 – qi-2yi-1

Contoh.

  1. Tentukan (42823,6409) dan tentukan selesaian kombinasi linearnya.

42823 x + 6409 y = 17

Jawab

Tabel untuk masing-masing konstanta adalah

i qi+1 ri xi yi
-1 42823 1 0
0 6 6409 0 1
1 1 4369 1 -6
2 2 2040 -1 7
3 7 289 3 -6-2(7)=-20
4 17 17 -1-7(3)=-22 7-7(-20)=147
5 0

Diperoleh  (42823,6409) = 17 dan 17 = 42823(-22) + 6409(147)



Komentar
  1. tetti sartika mengatakan:

    mkacih,,,,,it sgt membantu q

  2. Rusliansyah mengatakan:

    Terimakasih ya. Tapi bagaimana cara membuktikan “Misal a dan b adalah bilangan bulat ganjil yang bernilai positif. Jika a tidak membagi b, maka terdapat bilangan bula s dan t yang memenuhi a = bs + t, dimana t ganjil dan mutlak t < b"?

Tinggalkan Balasan

Isikan data di bawah atau klik salah satu ikon untuk log in:

Logo WordPress.com

You are commenting using your WordPress.com account. Logout / Ubah )

Gambar Twitter

You are commenting using your Twitter account. Logout / Ubah )

Foto Facebook

You are commenting using your Facebook account. Logout / Ubah )

Foto Google+

You are commenting using your Google+ account. Logout / Ubah )

Connecting to %s