Selamat datang di ForSa! Forum diskusi seputar sains, teknologi dan pendidikan Indonesia.

Welcome to Forum Sains Indonesia. Please login or sign up.

Maret 28, 2024, 07:09:45 PM

Login with username, password and session length

Topik Baru

Artikel Sains

Anggota
Stats
  • Total Tulisan: 139,653
  • Total Topik: 10,405
  • Online today: 112
  • Online ever: 1,582
  • (Desember 22, 2022, 06:39:12 AM)
Pengguna Online
Users: 0
Guests: 133
Total: 133

Aku Cinta ForSa

ForSa on FB ForSa on Twitter

Algoritma Euklid / Algoritma Euclidean

Dimulai oleh biobio, Juli 10, 2009, 06:09:16 PM

« sebelumnya - berikutnya »

0 Anggota dan 1 Pengunjung sedang melihat topik ini.

biobio

Adalah algoritma untuk menentukan GCD (great common divisor) alias FPB dari dua bilangan bulat a dan b atau secara matematika ditulis GCD(a,b).
* d = GCD(a,b)↔  1. d│a dan d│b
   2. Jika e│a dan e│b maka e│d
* a dan b adalah relatif prima atau koprima jika GCD(a,b) = 1
* Jika d = GCD(a,b)  maka 1. GCD (a/b, b/d) = 1
   2. GCD(a,b) = GCD(a+c.b,b)
* a│c dan b│c dengan GCD(a,b)=1, maka ab│c
* Lemma Euklid, jika a│bc dan GCD(a,b)=1 maka a│c

Dan bisa didefinisikan (secara formal) berdasarkan dua aturan umumnya:
Jika b│a, maka GCD(a,b) = b
Jika a = bt + r untuk t dan r adalah bilangan bulat, maka GCD(a,b) = GCD(b,r)
"The pen is mightier than the sword"

Nabih

Biasa dibuktikan ga lemma euclidnya, jujur saya masih  sangat bingung

Zanra_GTG

misal FPB 18 30, maka

a mod b = c
b mod c = d

dst sampai hasil akhir 0; dan jawaban dari FPBx adalah yg di samping kanan mod
30 mod 18  = 12
18 mod 12 = 6
12 mod 6 =0

dalam kasus ini disamping kanan mod yang terakhir adalah 6

sebetulnya masih ada algoritma stein, coba deh buka wordpress saya, tapi gak pernah saya update : [pranala luar disembunyikan, sila masuk atau daftar.]