CARA MENCARI FPB DAN KPK DENGAN ALGORITMA EUCLID
Oleh
Sulis Setiyawati
SEKOLAH TINGGI KEGURUAN DAN ILMU PENDIDIKAN
PERSATUAN GURU REPUBLIK INDONESIA
SIDOARJO
Abstrak
Dalam karya tulis ini akan membahas macam macam cara mencari FPB dan KPK dengan berbagai metode. Yaitu dengan cara faktor persekutuan atau kelipatan persekutuan, faktorisasi prima dan yang terakhir algoritma euclid. Berbagai macam metode tersebut akan mempermudah kita dalam mencari FPB dan KPK. Dari semua metode tersebut sudah dilengkapi soal dan pembahasan.
PENDAHULUAN
Matematika sebagai salah satu ilmu pengetahuan merupakan salah satu sarana untuk meningkatkan kemampuan berpikir setiap orang. Salah satu materi yang menjadi dasar matematika sekolah adalah bilangan. Seperti pada materi FPB dan KPK yang diajarkan dari tingkat SD sampai SMP. Konsep FPB dan KPK sering kali disajikan sangat mendasar. Sebagai contoh untuk menentukan FPB dan KPK cenderung menggunakan konsep pohon faktor. Pada karya tulis ini, penulis mencoba menghubungkan konsep konsep yang lain untuk menentukan FPB dan KPK dengan algoritma euclid. Metode ini diharapkan bisa menjadi alternatif bagi para pembaca untuk menambah wawasan tentang konsep konsep matematika secara utuh.
Kata kunci : FPB, KPK, Algoritma Euclid.
PEMBAHASAN
PENGERTIAN FPB DAN KPK
Kita mengetahui bahwa faktor faktor dari 30 adalah 1,2,3,5,6,10,15 dan 30. Dan faktor faktor dari 105 adalah 1,3,5,7,15,21,35, dan 105. Maka { 1,3,5 dan 15 } disebut faktor persekutuan ( pembagi bersama ) dari 30 dan 105. Kita biasa menyebutnya dengan FPB ( faktor persekutuan terbesar ).
Apabila A himpunan kelipatan positif dari 5 yaitu { 5,10,15,20,25,30,35 . . .} dan B adalah kelipatan positif dari 3 yaitu { 3,6,9,12,15,18,21,24,27 . . . }. Maka irisan A dan B, yaitu A  B = { 15, 30, 45 . . .} adalah himpunan semua kelipatan persekutuan dari 3 dan 5. Faktor terkecil dari 3 dan 5 disebut KPK.
MACAM MACAM CARA MENCARI FPB DAN KPK
Untuk mencari FPB dan KPK perlu mengetahui tentang bilangan prima dan  faktorisasi prima. Bilangan Prima  merupakan bilangan asli yang hanya mempunyai dua faktor yaitu bilangan itu sendiri dan 1, yang termasuk dalam bilangan prima {2,3,5,7,11,…..}. sedangkan faktorisasi prima merupakan penguraian bilangan menjadi perkalian faktor faktor prima. Untuk mencari faktor prima di perlukan pohon faktor.
CARA MENCARI FPB
Faktor Persekutuan Terbesar (FPB) merupakan bilangan bulat positif terbesar yang dapat membagi habis kedua bilangan tersebut. Ada beberapa metode untuk mencari FPB yaitu :
1.      Menggunakan Faktor Persekutuan
Faktor persekutuan merupakan faktor yang sama dari 2 bilangan atau lebih. FPB sendiri adalah nilai paling besar dari faktor persekutuan 2 bilangan atau lebih.
Contoh : carilah FPB dari 4, 8 dan 12
Penyelesaian :
Faktor dari 4 { 1, 2, 4 }
Faktor dari 8 { 1, 2, 4, 8 }
Faktor dari 12 { 1, 2, 3, 4, 6, 12 }
Faktor persekutuannya adalah { 1, 2, 4 }
Nilai yang terbesar adalah 4. Jadi FPB dari 4, 8 dan 12 adalah 4

2.      Menggunakan Faktorisasi Prima
Pada cara ini di ambil bilangan faktor yang sama , selanjutnya ambil angka terkecil dengan pangkat terkecil.
Contoh :
Carilah FPB dari 4, 8, dan 12
Penyelesaian :
Faktor prima dari 4 = 2²
Faktor prima dari 8 = 2³
Faktor prima dari 12 = 2² x 3
Faktor yang sama dari 4, 8 dan 12 adalah 2. Dengan pangkat terkecil yaitu 2² = 4. Jadi FPB = 4

Contoh soal :
1.      Carilah FPB dari 10, 15 dan 30. Dengan cara faktor persekutuan dan faktorisasi prima.
Penyelesaian :
Dengan faktor persekutuan
Faktor dari 10 { 1,2,5,10 }
Faktor dari 15 { 1,3,5,15 }
Faktor dari 30 { 1,2,3,5,6,10,15,30 }
Faktor persekutuan { 1,5 }. Nilai yang terbesar adalah 5. Jadi FPB dari 10, 15 dan 30 = 5
Penyelesaian dengan faktor prima :
Faktor prima dari 10 = 2 x 5
Faktor prima dari 15 = 3 x 5
Faktor prima dari 30 = 2 x 3 x 5
Faktor yang sama dari 10, 15 dan 30 adalah 5. Jadi FPB = 5

CARA MENCARI KPK
Kelipatan persekutuan terkecil (KPK) merupakan bilangan bulat positif terkecil yang habis dibagi oleh kedua bilangan tersebut. Ada beberapa cara untuk mencari KPK. Yaitu :
1.      Menggunakan Kelipatan Peersekutuan
Kelipatan persekutuan merupakan kelipatan yang sama dari 2 bilangan. KPK adalah nilai terkecil dari persekutuan 2 bilangan.
Contoh : carilah nilai KPK dari 8 dan 16
Penyelesaian :
Kelipatan 8 { 8,16,24,32,40 . . .}
Kelipatan 16 { 16,32,48,64 . . .}
Kelipatan persekutuan terkecil dari 8 dan 16 adalah 16. KPK = 16

2.      Menggunakan Fatorisasi Prima
Untuk mencari KPK dengan faktorisasi yaitu dengan mengalikan semua bilangan faktor. Apabila ada yang sama ambil nilai yang terbesar dengan pangkat terbesar. Dan dikalikan dengan nilai yang beda dari faktorisasi prima.
Contoh : carilan KPK dari 8, 12 dan 30.
Penyelesaian :
Faktor prima dari 8 = 2³
Faktor prima dari 12 = 2² x 3
Faktor prima dari 30 = 2 x 3 x 5
KPK = 2³ x 3 x 5 = 120
2 adalah faktor pesekutuan dari 8 ,12 dan 30. Diambil pangkat yang terbesar yaitu 2³.
3 dan 5 adalah nilai yang beda dari 8, 12 dan 30.
Contoh Soal :
1.      Ali berenang 10 hari sekali. Doni berenang 15 hari sekali. Sedangkan amar berenang setiap 20 hari sekali. Ketiga tiganya berenang secara bersamaan pada tanggal 20 februari 2013. Kapan ketiga tiganya berenang secara bersamaan untuk kedua kalinya ?
Penyelesaian :
Faktor prima dari 10 = 2 x 5
Faktor prima dari 15 = 3 x 5
Faktor prima dari 20 = 2² x 5
KPK = 2² x 3 x 5 = 60
Jadi mereka sama sama berenang setiap 60 hari sekali.
Mereka sama sama berenang untuk kedua kalinya = 20 + 60 = 80 hari. Atau 20 april 2013.

ALGORITMA EUCLID UNTUK MENCARI FPB DAN KPK
Algoritma euclid sering disebut sebagai algoritma pembagian. Suatu algoritma adalah suatu prosedur untuk memperoleh hasil dengan menerapkan berkali kali suatu operasi. GCD atau FPB dari 2 bilangan adalah suatu bilangan terbesar yang dapat membagi habis kedua bilangan tersebut. Misalkan terdapat 2 bilangan m dan n, maka GCD atau FPB dari 2 bilangan tersebut dapat dihitung dengan langkah berikut :
Bagi bilangan m dengan n dan anggap r adalah sisa bagi dari kedua bilangan tersebut. Nilai dari r akan memenuhi himpunan berikut : 0 = r  n . jika nilai r = 0 , maka algoritma selesai. Dan n adalah solusinya. Tapi jika tidak, maka nilai m = n, n = r. Kemudian kembali ke langkah awal.
Contoh :
m = 24 , n = 30. gcd = ( m, n )
24 / 30 = 0, r = 24
r ≠ 0 , maka
m = n , n = r
jadi m = 30 dan n = 24
gcd ( m, n ) :
30/ 24 = 1, r = 6
r ≠ 0 , maka
m = n , n = r
jadi m = 24 dan n = 6
gcd ( m , n ) :
24 / 6 = 4, r = 0
Karena r = 0, maka n adalah hasilnya
Jadi gcd ( 24,30) = gcd ( 30 , 24 ) = gcd ( 24 , 6 ) = 6
KPk adalah hasil kali kedua bilangan dikalikan dengan FPB dari kedua bilangan tersebut.
Contoh :
Tentukan KPK dari 8 dan 12
Penyelesaian :
( 8 x 12 ) / 4 = 24
4 adalah FPB dari 8 dan 12. Jadi KPK dari 8 dan 12 = 4

Contoh Soal :
1.      Tentukan FPB dan KPK dari ( 64,208 )
Penyelesaian :
( 208 , 64 )
208 = 3 x 64 + 16 ( 208 dibagi 64 adalah 3 dan sisanya 16 )
64 = 4 x 16 + 0 ( 64 dibagi 16 adalah 4 dan sisanya 0 )
Jadi FPB dari ( 64 , 208 ) = 16

Untuk mencari KPK, rumus yang digunakan adalah :
KPK ( A,B ) = A x B / FPB dari ( A,B )
Penyelesaian :
KPK dari ( 64 , 208 )
( 64 x 208 ) / 16 . ( 16 adalah FPB dari 64 dan 208 )
( 64 x 208 ) / 16 = 832
Jadi KPK = 832

KESIMPULAN
FPB adalah singkatan dari faktor persekutuan terbesar. Yaitu faktor pembagi yang terbesar dari suatu bilangan. Sedangkan KPK singkatan dari faktor pesekutuan terkecil. Yaitu kelipatan dari suatu bilangan yang nilai nya paling kecil. Untuk menentukan FPB dan KPK ada banyak metode yang bisa digunakan. Yaitu dengan faktor persekutuan atau kelipatan persekutuan, faktorisasi prima dan algoritma euclid. Semua metode ini diharapkan dapat meningkatkan wawasan tentang matematika secara luas dan utuh.

DAFTAR PUSTAKA
Wirasto, R.M., Ilmu Bilangan Aksiomatis jilid 1, Yogyakarta: FKIE IKIP Yogyakarta, 1973.
https: // istanamengajar,Wordpress.com/2013/06/03/soal-dan-pembahasan-algoritma-euclid.
http: // newidea39.blogspot.com2013/05/04/algoritma-fpb-dan-kpk-algoritma-euclid.html