Ketika SD, kita diajarakan mencari FPB (Faktor Persekutuan terBesar) dengan cara pemfaktoran. Nah… kali ini saya kan tunjukan cara lain mencari FPB tanpa pemfaktoran yang dinamakan Algoritma Euclid. Algoritma ini sudah ada 300 sm diambil dari nama matematikawan Yunani kuno, Euclid yang membuat Algoritma tersebut. Mungkin Algoritma Euclid adalah algoritma yang pertama kali dibuat Manusia.

Algoritma

Kita akan mencari FPB dari A dan B dangan A > B. Pertama-tama kita bagi A dengan B. Bilangan yang lebih kecil membagi bilangan yang lebih besar

A ÷ B = C sisa D

Artinya A dibagi B hasilnya adalah C dengan sisa D, kemudian sisa D ini membagi B

B ÷ D = E sisa F

lalu F membagi D

D ÷ F = G sisa H

Begitu seterusnya sampai kita mendapatkan sisa nol. Nah.. pembagi terakhir merupakan FPB dari A dan B

Contoh 1: Hitunglah FPB dari 77 dan 119

119 ÷ 77 = 1 sisa 42

77  ÷ 42 = 1 sisa 35

42  ÷ 35 = 1 sisa 7

35 ÷ 7 = 5 sisa 0

So… diperoleh FPB (77, 119) = 7

Contoh 2: Hitunglah FPB dari 168 dan 232

232 ÷ 168 = 1 sisa 64

168 ÷ 64 = 2 sisa 40

64 ÷ 40 = 1 sisa 24

40 ÷ 24 = 1 sisa 16

24 ÷ 16 = 1 sisa 8

16 ÷ 8 = 2 sisa 0

Diperoleh FPB(168, 132) = 8

Algorima Euclid bisa digunakan untuk menemukan FPB dari beberapa bilagan sekaligus. Misal kita mencari FPB dari bilangan-bilangan berikut

X₁, X₂, X₃ , … , X_n.

yang sudah diurutkan dengan X₁ terbesar dan X_n terkecil.
Pertama-tama kita mecari FPB(X_n-1, X_n) = A₁ kemudian FPB(X_n-2,A₁) =A₂ lalu FPB(X_n-3,A₂) =A₃, begitu seterusnya. sampai mendapat FPB(X₁, A_n-2) =A_n-1. Nah.. A_n-1 adalah FPB dari X₁, X₂, X₃ , … , X_n.

Contoh 3: Carilah FPB dari 126, 144 dan 171. Pertama-tama kita akan mencari FPB dari 126 dan 144.
144 ÷ 126 = 1 sisa 18
126 ÷ 18 = 7 sisa 0

Diperoleh FPB(126, 144) = 18. Selanjutnya dicari FPB dari 171 dan 18
171 ÷ 18 = 9 sisa 9
18 ÷9 = 2 sisa 0
Itu berarti FPB dari 126, 144 dan 171 adalah 9