Algoritma Euclidean (GCD)

Hitung Pembagi Persekutuan Terbesar (PBT) dari dua bilangan menggunakan algoritma Euclidean langkah demi langkah.

Angka

Nomor A

Nomor B

Analisis GCD

Pembagi Persekutuan Terbesar

Kelipatan Persekutuan Terkecil23562

Rasio Sederhana51 : 22

Iterative Process

1.1071=(2 × 462)+147

2.462=(3 × 147)+21

3.147=(7 × 21)+0Done!

Algoritma Euclidean

Algoritma Euclidean adalah metode yang efisien untuk menghitung pembagi persekutuan terbesar (GCD) dari dua bilangan bulat. Hal ini didasarkan pada prinsip bahwa KPK dari dua bilangan juga membagi selisihnya. Secara khusus, GCD(a, b) = GCD(b, a mod b). Mengulangi hal ini hingga sisanya nol akan menampilkan GCD.

💡

Pro Tips

GCD dari dua bilangan apa pun selalu minimal 1.
Jika GCDnya 1, bilangan tersebut dikatakan 'koprima' atau 'relatif prima'.
Algoritma ini digunakan dalam kriptografi modern, khususnya pada algoritma enkripsi RSA.

Fun Facts

"Algoritma Euclid adalah salah satu algoritma numerik tertua yang masih umum digunakan, muncul dalam 'Elemen' Euclid sekitar 300 SM."
"Algoritmenya dapat divisualisasikan dengan menyusun persegi panjang dengan persegi."
"Teorema Lamé menyatakan bahwa jumlah langkah dalam algoritma paling banyak adalah 5 kali jumlah digit pada bilangan yang lebih kecil."

Formula: a = q * b + r

Used with this

Similar tools that might be useful

Pengonversi Bentuk Bilangan Kompleks

Konversi antara bentuk bilangan kompleks persegi panjang (a + bi) dan polar (r∠θ).

Kalkulator Segitiga AAA

Analisislah proporsionalitas dan kesebangunan segitiga jika ketiga sudutnya diketahui.

Kalkulator Segitiga AAS

Selesaikan segitiga jika dua sudut dan satu sisi yang tidak termasuk diketahui.