coratcoret: Oktober 2016

BAB 1

PENDAHULUAN

A. Latar Belakang

Keterbagian (divisibility) merupakan bahan dasar dalam uraian lebih lanjut tentang pembahasan teori bilangan. Setelah pembahasan tentang FPB dan KPK, sifat-sifat dasar keterbagian dapat diperluas menjadi lebih lengkap dan mendalam. Demikian pula pembahasan tentang FPB dan KPK beserta sifat-sifatnya dapat lebih dikembangkan dan dikaitkan dengan keterbagian. Penerapan algoritma Euclides dalam pembahasan FPB dan KPK merupakan bahan yang memberikan peluang kemudahan untuk mencari FPB dan kpk dari bilangan-bilangan yang relative besar, dan untuk menyatakan suatu FPB sebagai kombinasi linier dari bilangan-bilangan komponennya.

B. Rumusan Masalah

1. Bagaimana menjelaskan mengenai keterbagian bilangan bulat ?

2. Bagaimana menjelaskan Faktor Persekutuan Terbesar ?

3. Bagaimana menjelaskan Kelipatan Persekutuan Terkecil ?

C. Tujuan

1. Memahami mengenai keterbagian bilangan bulat

2. Memahami Faktor Persekutuan Terbesar

3. Memahami Kelipatan Persekutuan Terkecil

BAB II

PEMBAHASAN

A. Sifat-Sifat Keterbagian

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)

Jika suatu bilangan bulat dibagi oleh suatu dilangan bulat yang lain, maka hasil pembagiannya adalah bilangan bulat atau bukan bilangan bulat. Misalnya jika 30 dibagi 5 maka hasil baginya adalah bilangan bulat 6; tetapi jika 30 dibagi 4, maka hasil baginya adalah 7,5 bukan bilangan bulat. Keadaan inilah yang mendasari definisi keterbagian.

1. Definisi 2.1

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.

3) –6 │ 42, karena ada bilangan bulat 7 sedemikian sehingga

42 = (7)-6

4) –5 │-25, karena ada bilangan bulat 5 sedemikian sehingga

–25 = (5)-5

5) 3 ┼ 5 karena tidak ada bilangan bulat x sedemikian sehingga

5 = (x) 3

6) 4 ┼ 9 karena tidak ada bilangan bulat y sedemikian sehingga

9 = (y) 4

7) –2 ┼ 11 karena tidak ada bilangan bulat z sedemikian sehingga

11 = (z)-2.

8) 7 │7 karena ada bilangan bulat 1 sedemikian sehingga 7 = (1) 7.

Jika y │ x dan 0 < y < x, maka y disebut pembagi murni dari x. Notas a^k ║ x tetapi a^k+1 ┼ x. Berdasarkan definisi 1 diatas selanjutnya pembagian dalam Z dapat dilakukan tanpa memperluas Z menjadi Q. Kemudian jika x,y

Z dan yx = 0, maka x= 0 atau y = 0 dan dikatakan bahwa Z tidak mempunyai pembagi nol. Akibatnya dengan sifat ini dapat dilakukan suatu penghapusan (Kanselasi).

Jika x,y

Z dan 5x = 5y, maka 5x – 5y = 0

5(x-y) = 0, diperoleh 5 = 0 atau x-y = 0, → x = y

Jadi persamaan 5x = 5y menjadi x = y tidak diperoleh dengan perkalian 1/5 , karena 1/5 bukan bilangan bulat.

Untuk selanjutnya pernyataan y ‌ x sudah dianggap bahwa y ≠ 0. Sehingga dari definisi 2.1 dapat ditentukan bahwa:

1) 1 │ x, untuk setiap x

Z, karena ada p

Z sedemikian sehingga

x = (p)1, sehingga 1 │ 3, 1│6, 1 │ 11, 1 │-21, 1 │16, 1 │ -10, semuanya bernilai benar.

2) y │ 0, untuk setiap y

Z dan y ≠ 0 karena ada 0

Z sehingga

0 =(y)0, sehingga 3 │ 0, 1│0, -1│ 0, 12 │0, -191 │0, 4│ 0, semuanya bernilai benar.

3) x │x untuk setiap x

Z dan x ≠ 0, karena ada 0

Z, sehingga

x = (1)x, sehingga pernyataan-pernyataan 2│2, -2│-2, 42│42, 12│12, -20│-20, 21│21, semuanya bernilai benar.

4) Jika y │x, maka kemungkinan hubungan antara y dan x adalah y < x, y = x, y>x. Misalnya 2 │ 2 dengan 2 = 2, 2 │4 dengan 2 < 4, dan

2 │ -4 dengan 2 > -4.

Dalil 2.1

Jika a,b,c

Z maka berlaku:

· Dalil 2.1.a

a│ b → a │bc, untuk setiap c

Pembuktian :

Karena diketahui a│ b , maka menurut definisi 1 ada suatu bilangan bulat p sedemikian sehingga b = (p)a. b = pa berarti bc = (pa)c. Hal ini berarti terdapat bilangan bulat q = pc sedemikian sehingga bc = qa.

Jadi a │bc.

· Dalil 2.1.b

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

Pembuktian:

a │b → b = pa, untuk suatu p

b │c → c = qb, untuk suatu q

( b = pa, c = qb) → c = q(pa) atau c = (qp)a. atau c = wa, untuk suatu w

Jadi a │c.

· Dalil 2.1.c

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

Pembuktian:

a │b → b = pa, untuk suatu p

b │a → a = qb, untuk suatu q

( b = pa, a = qb) → a = q(pa) atau a = (qp)a. Karena a │b, berarati

a ≠ 0, sehingga a = (qp)a atau a(1-qp) = 0 dan dapat disederhanakan menjadi a=0 atau qp = 1.

qp = 1 → ( q = 1 dan p =1) atau ( p = -1 dan q = -1)

p = q = 1 maka a = pb = b ....(1)

p = q = -1, maka a = pb = -b ...(2)

Dari (1) dan (2) didapat a = ± b

· Dalil 2.1.d

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

Pembuktian:

a │b → b = pa, untuk suatu p

a │c → c = qa, untuk suatu q

( b = pa, c = qa) → b ± c = pa ± qa atau b ± c = a ( p ± q)

b ± c = at dengan t

Jadi a │b ± c

· Dalil 2.1.e.

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

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

Pembuktian:

1. a │b → b = pa, untuk suatu p

a │c → c = qa, untuk suatu q

bx + cy = ( pa)x + (qa)y

bx + cy = a (px+qy) dengan (px + qy)

Jadi a │(bx+cy).

· Dalil 2.1.f

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

Pembuktian:

a │b → b = pa, untuk suatu p

karena a > 0, b > 0 dan b = pa maka p > 0.

karena p

Z maka p bukan suatu pecahan.

Sehingga nilai kemungkinan x adalah 1,2,3, ..., yaitu x = 1 atau x >1

b = pa dan p =1 → b = a atau a = b

b = pa dan p > 1 → b > a atau a < b.

a = b atau a < b → a = b

· Dalil 2.1.g

a │b ↔ ma │ mb untuk setiap m

Z dan m ≠ 0

pembuktian:

(a) a │b → b = pa, untuk suatu p

→ mb = map → mb = (ma)p → ma │mb

(b) ma │mb → mb = (ma)p untuk suatu p

Z→ ma │mb

mb = m (ap) dan m ≠ 0 → b = ap → a │b

b │c → c = q b, untuk suatu q

· Dalil 2.1.h

( a│b dan a │ b+c ) → a │c.

Pembuktian :

a │b → b = pa, untuk suatu p

a │b + c → b + c = qa, untuk suatu q

b + c = qa → c = qa – b.

c = qa – b dan b = pa → c = qa - pa atau c = a( q-p)

c = a ( q-p) dengan (q-p)

Z → a │c.

Dalil 2.2 (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

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

Jika r

a maka r – a

r = b – qa

r – a = b – qa – a

= b – ( q +1) a.

r – a

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

r – a

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

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 q₁, q₂, r₁, r₂

Z dan memenuhi hunbungan persamaan

b = q₁a + r₁

b = q₂a + r₂

Sehingga berlaku q₁a+ r₁ = q₂a+ r₂

( q_{1 -}q₂) a + ( r₁ - r₂ ) = 0 .

( r₁ - r₂ ) = ( q_{2 –}q₁)a

a │ ( r₁ - r₂ )

r₁ - r₂ = 0 atau r₁ - r₂

a ( a

r₁ - r₂ )

r₁ - r₂ = 0

r₁ = r₂

(q_{1 -}q₂) a = 0

q₁ = q₂

r₁ - r₂

a > 0, r₁ > 0 , r₂ > 0

r₁ a = 0.

Jadi r₁ = r₂ dan q₁ = q₂ 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).

2. Definisi 2.2

Jika b = qa + r dengan 0 ≤ r < a, maka

b disebut bilangan yang dibagi (devidend)

a disebut bilangan pembagi (devisor/faktor)

q disebut bilangan hasil bagi (quotient), dan

r disebut bilangan sisa (remainder/residu)

Dalil 2.2 di atas disebut pula dengan dalil algoritma pembagian. Algoaritma adalah prosedur atau metode matematis untuk memperoleh hasil tertentu yang dilakukan menurut sejumlah langkah berurutan yang berhingga. Dalil 2 ini sebenarnya lebih bersifat dalil eksistensi (keujudan) dari adanya bilangan-bilangan bulat q dan r dari suatu algortima. Namun demikian uraian tentang pembuktiannya dapat memberikan gambaran adanya suatu metode, cara , atau prosedur matematis untuk memperoleh bilangan-bilangan bulat q dan r sehingga b = qa + r.

Jika a = 2 dan b adalah sebarang bilangan bulat, maka menurut dalil sebelumnya b dapat dinyatakan dengan b = 2q + r, dengan 0 ≤ r < a. Hal ini berarti bahwa nilai-nilai b yang mungkin dapat ditentukan oleh nilai-nilai r yang mungkin yaitu r = 0 dan r = 1.

Untuk r = 0 maka b = 2q + r = 2q + 0.

b = 2q, dengan q

b yang dapat dinyatakan dengan 2q ( q

Z ) disebut bilangan bulat genap (even integer).

Untuk r = 1, b = 2q + r = 2q + 1 ( q

Z ) disebut bilangan bulat ganjil. (odd intereger, gasal).

Ternyata berdasarkan dalil algoritma pembagian, setiap bilangan bulat dapat dinyatakan sebagai bilangan bulat genap (2q) atau bilangan bulat ganjil ( 2q + 1). Selanjutnya jika diambil a = 3, maka menurut dalil Algoritma Pembagian, dengan mengambil r= 0, r=l dan r=2. Sehingga sebarang bilangan bulat b dapat dinyatakan sebagai bentuk dari salah satu persamaan berikut:

b = 3q

b = 3q + 1

b = 3q + 2

Dengan alasan yang sama, setiap bilangan bulat selalu dapat dinyatakan antara lain:

Salah satu dari 4q, 4q+1, 4q+2, 4q+3 (q Z)
Salah satu dari 5q, 5q+1, 5q+2, 5q+3, 5q+4 (q Z)
Salah satu dari 6q, 6q+1, 6q+2, 6q+3, 6q+4, 6q+5 (q Z)

Disinilah sebenarnya letak dari konsep algoritma pembagian, suatu konsep mendasar yang dapat digunakan untuk membantu pembuktian sifat-sifat tertentu.

Contoh:

1. Diketahui n adalah bilangan bulat, buktikan bahwa 2 │n³ – n .

Bukti:

Menurut dalil Algoritma pembagian, terdapat bilangan bulat q sedemikian sehingga n = 2q atau n = 2q + 1,

Untuk n = 2q maka

n³ – n = n (n² – 1)

= n(n-1)(n+1)

= 2q(2q-1)(2q+1)

= 2{q(2q-1)(2q+1)

n³ – n = 2{q(2q-1)(2q+1)

Sehingga 2 │2{q(2q-1)(2q+1) atau 2 │ n³ – n

Untuk n = 2q+1 maka

n³ – n = n (n² – 1)

= n(n-1)(n+1)

= (2q+1)(2q+1-1)(2q+1+1)

= (2q+1)(2q)(2q+2)

n³ – n = (2q+1)(2q)(2q+2)

Sehingga 2 │(2q+1)(2q)(2q+2) atau 2 │ n³ – n

2. Tunjukkan bahwa 4 ┼ n² + 2 untuk sebarang n

Jawab

Dengan bukti tidak langsung, anggaplah 4 │ n² + 2.

Sesuai dengan dalil algoritma pembagian, untuk n

Z dapat dinyatakan sebagai

n = 2q atau n = 2q + 1, q

Untuk n = 2q, maka n² + 2 = (2q)²+ 2 = 4q² + 2

4 │n² + 2

n² + 2 = 4q² + 2

4 │4q² + 2

4 │4q² , maka 4 │2, hal ini terjadi kontradiksi karena 4 ┼ 2.

Jadi anggapan bahwa 4 │ n² + 2. adalah salah sehingga 4 ┼ n² + 2.

Untuk n = 2q + 1, maka n² + 2 = (2q+1)² + 2 = 4q² + 4q + 3

= 4(q²+q) + 3

4 │n² + 2

n² + 2 = 4(q² +q) + 3

4 │4(q² + q) + 3

4 │4(q² + q), maka 4 │3, hal ini terjadi kontradiksi karena 4 ┼ 3.

3. Definisi 2.3

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.

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 2.3

Jika d = (x,y) maka d adalah bilangan bulat positip terkecil yang mempunyai bentuk umum a_ox + b_oy dengan a_o, b_o

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 = a_o dan b = b_o sehingga t = a_ox + b_oy 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(a_ox + b_oy)

r = ( 1-a_oq)x + (-b_oq)y

r = a₁x + b₁y dengan a₁ = 1-a_oq

Z, dan

b₁ = -b_oq

Jadi r = a₁x + b₁y

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

S sehingga x = dp.

d = (x,y) berarti d │ y sehingga

S sehingga y = dp.

t = a_ox + b_oy

= a_o (dp) + b_o (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 = a_ox + b_oy

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

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

Dalil 2.4

Jika t

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

Bukti

Sesai dengan bukti dalil 1 di atas, maka:

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

= atx + bty

= t (ax + by)

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

= t (ax +by)

Dalil 2.5

Jika x,y

Z dan d = (x,y) maka (

) = 1

Bukti :

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

(x,y) = (d.

, d.

) = d (

)

Karena d > 0 maka d (

) atau 1 = (

)

Dengan demikian (

) = 1

Dalil 2.6

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

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.

Dalil 2.7

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

Bukti:

(x,t) = 1 → terdapat a_o dan b_o

Z sedemikian sehingga a_ox+b_ot=1

(y,t) = 1 → terdapat a_o dan b_o

Z sedemikian sehingga a₁y+b₁t=1

a_ox+b_ot=1 → a_ox = 1 - b_ot

a₁y+b₁t=1 → a₁y = 1 - b₁t

a₁x = 1 - b_ot dan a₁y = 1 - b₁t maka:

(a_ox)(a₁y) = (1 - b_ot)(1 - b₁t)

= 1- (b_o- b₁+ b_ob₁t)t

(a_oa₁)(xy) = (1- b₂)t atau (xy) a₂+b₂t=1 dengan

a₂= a_oa₁ dan b₂= b_o- b₁+ b_ob₁t

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

Dalil 2.8

Ditentukan x,y

Z , (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,b

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)

Dalil 2.9

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)

Perhatikan bahwa:

1. (6,15) = (15,6) = (6, -15) = (-6,15) = 3.

2. (4,6) = ( 4, 3.4 + 6) = ( 4,18) = 2

3. (3,5) = ( 3, 5.2 + 1) = ( 3, 11) = 1

4. (15, 81) = ( 15, 6 + 75) = ( 15, 6 + 5.15) = ( 6, 15) = 3.

Dalil 2.10 (Dalil Algoritma Euclides)

Jika r₁, r₂

Z, dan r₁ > r₂ dan dengan proses algoritma pembagian dibentuk Suatu barisan menurun bilangan bulat r₁, r₂, r₃, ... , r_k-1, r_k, r_k+1=0

Yaitu:

r₁ = q₁r₂ + r₃ , 0 ≤ r₃ < r_2.

r₂ = q₂r₃ + r₄ , 0 ≤ r₄ < r_2.

r₃ = q₃r₄ + r⁵ , 0 ≤ r₅< r_2.

r₄ = q₄r₅ + r₆ , 0 ≤ r₆ < r_2.

.............................................

r_k-2 = q_k-2r_k-1+ r_k , 0 ≤ r_k < r_2.

r_k-1= q_k-1r_k + r_k+1, r_k+1= 0

Maka (r₁,r₂) = r_k.

Bukti.

(r₁,r₂) = (q₁r₂+ r₃, r₂) ....................... (substitusi r₁)

= (r₃,r₂) ........................ (teorema)

= (r₃, q₂r₃+ r₄) ........................ (substitusi r₂)

= (r₃,r₄)

.......

= (r_k,r_k+1)

= (r_k,0) .......................... (r_k+1 = 0)

(r₁,r₂) = r_k

Contoh

1. Tentukan (105,60) dan nyatakan hasilnya sebagai bentuk kombinasi linear

ax + by = c, dimana c = (a,b).

Dengan Algoritma Euclides diperoleh:

105 = (1) 60 + 45

60 = (1) 45 + 15

45 = (3) 15 + 0, sehingga diperoleh (105,60) = 15.

Selanjutnya dengan jalan mundur diperoleh:

15 = 60 – 45 (1)]

= 60 – [105 – 60(1)]

= 60 – 105 + 60 (1)

= (-1) 105 + (2) 60.

Akhirnya diperoleh (105,60) = (-1)105 + (2) 60.

5. Dengan cara yang sama diperoleh

(570, 1938) = 114

114 = 570 – 2 (228)

= 570 – 2 [1938 – 3.570]

= 570 – 2 (1938) + 6(570)

= 7 (570) – 2 (1938)

= -2(1938) – 7(570).

4. Definisi 2.4

Misalkan a dan b adalah bilangan-bilangan bulat. m adalah kelipatan persekutuan dari a dan b jika dan hanya jika a | m dan b | m.

Nol adaah suatu kelipatan persekutua dari a dan b. Ab dan –ab masing-masing juga merupakan suatu kelipatan persekutuan dari a dan b. Jadi himpunan semua keipatan persekutuan ulat positif dari a dan b tdak ernah sama dengan himpunan kosong.

Himpun semua kelipatan bulat positif dari 6 adalah (6,12,18,24....)

Himpunan semua kelipatan bulat positif dari -9 adalah (9,18,27,36,...)

Jadi himpunan semua kelipatan persekutuan dari 6 dan -9 adalah (18,36,54,72, . . .)

Sehingga kelipatan persekutuan terkecil dari 6 dan -9 adalah 18.

Ingat bahwa dalam himpunan bagian dari himpunan-himpunan bilangan bulat positif selalu mempunyai anggota terkecil. Sehingga KPK dari setiap ilangan bulat selalu ada.

Secara formal, KPK dari dua bilangan bulat didefinisiskan sebagai berikut :

Dalil 2.11

Ditentukan x, y ϵ z, x ≠ 0, dan y ≠ 0.

m = {x,y} jika dan hanya jika x l m, y l m, m > 0 dan untuk sebarang kelipatan persekutuan n dari x dan y berlaku m l n.

Bukti :

Ambil m = {x,y}, maka menurut definisi, jelas bahwa x l m,y l m, dan m > 0 misalkan n adalah sebarang kelipatan persekutuan dari x dan y, maka x l n dan y l n. harus ditunjukkan bahwa m l n.

Karena m adalah kelipatan persekutuan terkecil dari xdan y, dan n adalah sebarang kelipatan persekutuan dari x dan y, maka m l n.

Menurut pembagian algoritma, jika m ≤ n, maka tentu ada q, r ϵ z sehingga :

n = qm + r . 0 ≤ r < m.

untuk membukti nm l n, harus ditunjukkan bahwa n =qm, harus ditunjukkan bahwa r = 1.

Perhatikan bahwa n = qm + r, makan r = n – qm

(x l m dan y l m → x ϵ qm dan y ϵ qm)

(x ϵ n dan x ϵ qm) → x l (n – qm)

(y ϵ n dan y ϵ qm) → y l (n – qm)

{x l (n - qm) dan (y l (n – qm) → (n – qm} adalah kelipatan persekutuan x dan y

{r = n – qm, x l (n – qm), dan y l (n – qm)} → (x l r dan y l r)

{x l r dan y l r} → r adalah kelipatan persekutuan dari x dan y karena r dan m adalah kelipatan-kelipatan persekutuan dari x dan y, dan m adalah yang terkecil, serta 0 ≤ r < m, maka jelas bahwa r = 0, sehingga n = qm atau m l n.

Ambil m > 0, x l m,y l m, dan untuk sebarang n kelipatan persekutuan dari x dan y, berlaku m l n.

Ini berarti bahwa m adalah suatu kelipatan persekutuan dari x dan y yang membagi semua kelipatan persekutuan dari x dan y yang lain.

Jadi : m = [x,y]

Perhatikan bahwa :

[2,3] = 6 dan [6,9] = [3,2,3,3] = 18 = 3,6

[2,5] = 10 dan [8,20] = [4,2,4,5] = 40 = 4,10

[3,5] = 15 dan [30,50] = [10,3,10,5] = 150 = 10,15

Adakah suatu kecenderungan pola tertentu ?

Dalil 2.12

Untuk sebarang m ϵ N berlaku [mx,my] = m[x,y]

Bukti :

Ambil K = [mx,my], dan k = [x,y]

K = [mx,my] → (mx l K dan my l K)

k = [x,y] → (x l k dan y l k)

x l k → mx l mk

y l k → my l mk

(mx mk dan my l mk) → mk adalah kelipatan persekutuan dari mx dan my karena K adalah kelipatan persekutuan terkecil dari mx dan my, dan mk adalah kelipatan persekutuan mx dan my, maka K l mk atau [mx,my] l m[x,y].

Mx l K → K = amx, a ϵ Z → Km = ax → x l Km

My l K → K = bmy, b ϵ Z → Km = by → y l Km

(x l Km dan y l Km→ Km adalah kelipatan persekutuan dari x dan y

→ [x,y] l Km

→ m[x,y] l mKm

→ m[x.y] l K

→ m[x,y] l [mx,my]

{ [mx,my] l m[x,y] dan m[x,y] l [mx,my] } → m[x,y] = [mx,my]

Jadi : m[x,y] = [mx,my].

Perhatikan sekarang beberapa keadaan berikut:

(2,3) = 1, [2,3] = 6, dan 2.3 = 6

(2,5) = 1, [2,5] =10, dan 2.5 = 10