Ide Di Balik Algoritma Euclid Untuk Mencari Faktor Persekutuan Terbesar - Belajar

Lost Password

Lost your password? Please enter your email address. You will receive a link and will create a new password via email.

Send Message

Add post

Username* Please type your username .

E-Mail* Please type your E-Mail .

Post Title* Please choose an appropriate title for the post .

Category* Please choose the appropriate section so easily search for your post .

Tags Please choose suitable Keywords Ex : post , video .

Attachment

Browse

Details

Add question

You must login to ask question.

Ide Di Balik Algoritma Euclid Untuk Mencari Faktor Persekutuan Terbesar

Riad Taufik Lazwardi excellent July 20, 2018 Matimatian Comments Off 2408 views

“Berapakah Faktor Persekutuan Terbesar dari 6 dan 3?” yups, 3. Caranya adalah kita tinggal membagi bilangan terbesar 6 dengan bilangan terkecil 3, ternyata tidak memiliki sisa hasil bagi. Sekarang bagaimana jika soalnya agak sulit, semisal kita akan mencari FPB dari bilangan 18 dan 12. Idenya adalah dengan menuliskannya sebagai berikut :

$18=1\times12+6$

1 adalah hasil bagi, 12 adalah pembagi dan 6 adalah sisa. Jika kita perhatikan persamaan diatas, fakta yang dapat diperoleh adalah

FPB(18,12) tak mungkin lebih dari 12.
FPB(18,12) yang mungkin adalah faktor dari 12, dengan harapan ada faktor dari 12 yang juga faktor dari 18.

Andai kita mengganti 12 pada persamaan di atas dengan $6\times 2$ maka akan diperoleh

$18=(6\times2)+6 \Rightarrow 18=6(2+1)\Rightarrow 18=6(3)$

Catatan : $"1\times$ ” pada $1 \times 12$ dihilangkan untuk mempermudah.

Dari persamaan di atas, 6 menjadi pembagi 18 dan sudah pasti 6 pembagi 12.

Jadi FPB(18,12)=6.

Penggantian $12$ dengan $6 \times 2$ adalah penggantian yang sangat brilliant lain hal bila kita menggantinya dengan $4\times 3$ , maka

$18=(4 \times 3)+6$

sehingga kita tidak akan memperoleh bilangan yang membagi 18.

Nah, penggantian 12 dengan $6 \times 2$ (yang merupakan faktornya) ini dipilih karena salah satu faktornya sama dengan sisanya, yakni 6.

Sekarang kita lanjut ke soal agak susah. Siapin kopi ya! andai nanti kamu ngantuk, silahkan tetesin kopi tadi ke mata, wkwk.

“Berapakah FPB(18,14)?”

$18= 1 \times 14 + 4$

Andai kita ganti 14 dengan $1 \times 14$ atau pun $2 \times 7$ kita tidak dapat memperoleh bilangan yang membagi 18.

$18= 1 \times 14 + 4$

$18= 2 \times 7 + 4$

Kecuali jika kita mengganti 14 dengan $2 \times 7$ dan juga mengganti 4 dengan $2 \times 2$ .

$18= 2 \times 7 + 2 \times2 \Rightarrow 18=2 (7+2)$

Secara tidak langsung kita telah memperoleh 2 sebagai faktor dari 14 , 4 dan juga 18.

Jadi FPB(18,14)=2

Langkah penggantian 14 dan 4 dengan perkalian faktor-faktornya sebetulnya bertujuan untuk mencari FPB(14,4) yang juga membagi 18.

Jadi, FPB(18,14)=FPB(14,4)

Secara umum,

$FPB(a,b)=FPB(b,s)$

*s adalah sisa.

Algoritma lengkap Euclid untuk mencari FPB(a,b) dengan $a\geq b$ dan r sisa :

$FPB(a,b)=FPB(b,r_0)=FPB(r_0,r_1)=\ldots=FPB(r_{n-1},r_n)$

*Hingga memperoleh sisa 0. Jika kita menuliskannya dengan formula rekursif, maka aka diperoleh

$a=q_0b+r_0$

$b=q_1r_0+r_1$

$r_0=q_2r_1+r_2$

hingga

$r_{n-2}=q_nr_{n-1}+r_n$

$r_{n-1}=q_nr_{n}+0$

$FPB(a,b)=r_{n}$

About Riad Taufik Lazwardiexcellent

"In the middle of difficulties lies oppoutunities"

Follow Me