Register Now

Login

Lost Password

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

Add post

Add question

Ide Di Balik Algoritma Euclid Untuk Mencari Faktor Persekutuan Terbesar

“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}

 

 

Baca Lagi Biar Pinter

  • 32
    Terkadang kita kesulitan untuk mengerjakan sesuatu secara langsung, tetapi kita dapat mengetahui apa yang terjadi jika kita dekati lebih dekat…
    Tags: $latex, $, ide

About Riad Taufik LazwardiSweet

Lecturer of Mathematics at 1. Bina Tunas Bangsa (now) 2. Fitrah Islamic World Academic School (2019-2020) 3. Kalbis Institute | Managed by Binus (2018-2019) 4. Telkom University (2017-2018) 5. UIN Bandung (2015-2018)

Follow Me