FPB dan KPK (Teorema Euclid)

Anda masih ingat dengan FPB dan KPK? mungkin ketika anda masih SD pernah belajar bagaimana cara mencari FPB dan KPK. Dulu pasti kalian menggunakan sebuah faktor untuk mencari sebuah FPB, namun cara itu tidak begitu efektif kalau kedua bilangan yang dicari FPBnya terlalu tinggi.

Kali ini saya akan membahas mengenai cara mencari FPB dan KPK menggunakan algoritma euclid. saya akan mengajarkan langsung menggunakan contoh.

FPB

FPB adalah mencari bilangan terbesar yang habis membagi A dan B.
Notasinya adalah FPB(A,B) = Mencari FPB a dan B.

Contoh :
FPB(64,208) = ?
FPB(208,64) = ? //Kita ubah dulu jadi kiri yang lebih besar.
208 = 3 * 64 + 16 // Jadi 208-nya kita bagi 64 dulu ternyata adalah 3 dan sisanya adalah 16.
64 = 4 * 16 + 0 // Lalu 64nya kita bagi dengan sisa dari atasnya yaitu 16, hasilnya adalah 4 dan ternyata habis.
Jadi FPB(208,64) = 16.

FPB(89401, 86273) = ?
89401 = 1 * 86273 + 3128;
86273 = 27 * 3128 + 1817;
3128 = 1 * 1817 + 1311;
1817 =  1 * 1311 + 506;
1311 = 2 * 506 + 299;
506 = 1 * 299 + 207;
299 = 1 * 207 + 92;
207 = 2 * 92 + 23;
92 = 4 * 23 + 0; //Jawabannya adalah 23.

Kesimpulan :
FPB(A,B) = ?
A = x*B + C;
B = y*C + D; //kalau D = 0, Maka C adalah jawabannya. jika tidak lanjutkan lagi.
C = z*D + E; //kalau E = 0, Maka D adalah jawabannya, jika tidak lanjutkan lagi. ya begitu terus :p

KPK

KPK adalah mencari bilangan terkecil yang habis dibagi oleh A dan B.

Ketika anda ingin mencari KPK saya ada satu rumus yang mungkin cukup berharga :p

KPK(A,B) = A * B / FPB(A,B); gak jelas? nih saya kasih :p

contoh?
KPK (64,208) =
(64.208) / 16  =
4. 208 = 832. Jadi KPKnya 832.

KPK(89401, 86273) =
(89401.86273) / 23 =
3887.86273 = 335 343 151.
Jadi KPKnya 335 343 151.

Sekarang kalian sudah lebih cepat menghitung FPB dan KPK kan? Kalau tidak percaya coba bandingkan dengan cara ketika kalian SD.

Jika kalian ingin berlatih saya berikan soal kerjakan dan bandingkan dengan jawaban saya.
Latihan 1

Semoga Membantu :p