Forum Sains Indonesia

Ilmu Alam => Matematika => Topik dimulai oleh: nash pada Mei 06, 2009, 05:22:27 PM

Judul: GCD tiga bilangan, mungkinkah?
Ditulis oleh: nash pada Mei 06, 2009, 05:22:27 PM
yang slama ini kutahu kan cuma GCD dua bilangan, cth: GCD(24,18).
nah, yg kutanya, kalo GCD tiga bilangan bisa ga yah?
cth: GCD(32, 16, 12)

mohon tanggapannya
Judul: Re: GCD tiga bilangan, mungkinkah?
Ditulis oleh: Mtk Kerajaan Mataram pada Mei 07, 2009, 12:10:51 PM
Maksudnya apa sebenarnya? Kalau GCD, jelas berapapun banyaknya bisa. Atau mungkin yang hubungannya dengan metode pencariannya :
Kalau dengan faktorisasi, maka berapapun bisa.
Kalau dengan algoritma euclid, maka harus per dua-dua bilangan, tapi pada intinya bisa juga.
Judul: Re: GCD tiga bilangan, mungkinkah?
Ditulis oleh: nash pada Mei 07, 2009, 08:32:48 PM
o iya?
waduh ilmuku blum sampe k sana neh,

gini ja, biar lbh jelas, bisa tolong jawab 2 soal brikut ni:
a. GCD (16, 24, 32)
b. GCD (16, 20, 24, 28)

btw, apakah jga bsa dterapkan mjadi persamaan diophantine?

trima kasih atas partisipasinya
Judul: Re: GCD tiga bilangan, mungkinkah?
Ditulis oleh: Mtk Kerajaan Mataram pada Mei 07, 2009, 09:22:58 PM
Apa tuh maksudnya jadi persamaan diophantine?
Persamaan Diophantine kan ini : x^n+y^n=z^n...

Mungkin maksud anda adalah dinyatakan sebagai kombinasi linear yang sama dengan GCD-nya, yaitu
a. p(16) + q(24) + r(32) = GCD (16, 24, 32)
b. p(16) + q(20) + r(24) + s(28) = GCD (16, 20, 24, 28)
Tentu saja bisa...

a.
Untuk 16 dan 24 dulu, yaitu :
1 x 24 + (-1) x 16 = 8 = GCD(16,24)         
Lalu hasil GCD ini dengan 32 :
1 x 32 + (-3) x 8   = 8 = GCD(8,32) = GCD (16, 24, 32)
Substitusikan yang di atas untuk menggantikan 8 sbb :
1 x 32 + (-3) x (1 x 24 + (-1) x 16) = 8
1 x 32 + (-3) x 24 + 3 x 16 = 8 = GCD (16, 24, 32)

b.
Untuk 16 dan 20 dulu, yaitu :
1 x 20 + (-1) x 16 = 4 = GCD(16,20)......(*)          
Lalu hasil GCD ini dengan 24 :
1 x 24 + (-5) x 4   = 4 =   GCD(4,24) = GCD (16, 20, 24)
Sulihkan (*) sbb :
1 x 24 + (-5) x (1 x 20 + (-1) x 16)   = 4 = GCD (16, 20, 24)
1 x 24 + (-5) x 20 + 5 x 16 = 4 = GCD (16, 20, 24) .....(**)
Lalu hasil GCD ini dengan 28 :
1 x 28 + (-6) x 4   = 4 = GCD (4, 28) = GCD (16, 20, 24, 28)
Sulihkan (**) sbb :
1 x 28 + (-6) x (1 x 24 + (-5) x 20 + 5 x 16) = 4 = GCD (16, 20, 24, 28)
1 x 28 + (-6) x 24 + 30 x 20 + (-30) x 16 = 4 = GCD (16, 20, 24, 28)

Mungkin itu maksudnya.... Semoga yang lain ikut mengambil paham.
Judul: Re: GCD tiga bilangan, mungkinkah?
Ditulis oleh: Nabih pada Mei 24, 2009, 06:44:13 PM
Ada cara selain algoritma euclid untuk menyelsaikan persamaan diophantene
Judul: Re: GCD tiga bilangan, mungkinkah?
Ditulis oleh: nash pada Mei 24, 2009, 09:16:21 PM
@nabih

pake apa?
Judul: Re: GCD tiga bilangan, mungkinkah?
Ditulis oleh: Nabih pada Mei 24, 2009, 09:51:55 PM
Maaf, saya tanya, kurang tanda tanya?
Judul: Re: GCD tiga bilangan, mungkinkah?
Ditulis oleh: futror pada Mei 27, 2009, 11:13:00 PM
Agar tidak ada perbedaan pemahaman, kita sepakati beberapa istilah dulu.

Persamaan Diophantine: persamaan di mana variabelnya hanya bisa memiliki nilai bilangan bulat.

a habis membagi b (a dan b bilangan bulat): artinya b/a adalah bilangan bulat.

GCD(a,b,c,...,n): bilangan bulat terbesar yang habis membagi a,b,c,..., dan n.

Saya cukup yakin definisi-definisi di atas sudah benar. Kalau Anda kurang yakin, silakan lihat di Wikipedia atau MathWorld. Sekarang kita akan mengerjakan dua soal di atas berdasarkan definisi-definisi tersebut.

a. GCD(16,24,32) adalah bilangan bulat terbesar yang habis membagi 16, 24, dan 32. Bilangan ini habis membagi 16 sehingga nilai-nilai yang mungkin adalah 1, 2, 4, 8, dan 16. Di antara bilangan-bilangan ini, bilangan terbesar yang habis membagi 24 adalah 8. Ternyata 8 juga habis membagi 32. Jadi GCD(16,24,32)=8.

b. GCD(16,20,24,28) habis membagi 16 sehingga nilai yang mungkin adalah 1, 2, 4, 8, 16. Dari bilangan-bilangan ini, bilangan terbesar yang habis membagi 20 adalah 4. Tetapi 4 juga habis membagi 24 dan 28. Jadi GCD(16,20,24,28)=4.

Dari sini, kita dapat membuat persamaan Diophantine 16x+24y+32z=8. Persamaan ini pasti punya solusi dalam bilangan bulat. Berapapun bilangan bulat (a,b,c), persamaan ax+by+cz=GCD(a,b,c) pasti punya solusi (x,y,z) dalam bilangan bulat. Ini dapat dibuktikan dari teorema Bézout.

-futror-
Judul: Re: GCD tiga bilangan, mungkinkah?
Ditulis oleh: Mtk Kerajaan Mataram pada Mei 29, 2009, 07:17:29 AM
Kutip dari: futror pada Mei 27, 2009, 11:13:00 PM
Agar tidak ada perbedaan pemahaman, kita sepakati beberapa istilah dulu.
Persamaan Diophantine: persamaan di mana variabelnya hanya bisa memiliki nilai bilangan bulat.
a habis membagi b (a dan b bilangan bulat): artinya b/a adalah bilangan bulat.
GCD(a,b,c,...,n): bilangan bulat terbesar yang habis membagi a,b,c,..., dan n.
Saya cukup yakin definisi-definisi di atas sudah benar. Kalau Anda kurang yakin, silakan lihat di Wikipedia atau MathWorld.
-futror-

Anda benar sekali. Mari meramaikan dan memajukan matematika.