Kalkulator Algoritma Euklides Diperluas

Kalkulator Algoritma Euklides Diperluas menghitung Faktor Persekutuan Terbesar (FPB) dari dua bilangan bulat dan menemukan koefisien Bézout — bilangan bulat s dan t yang memenuhi fpb(a, b) = s·a + t·b. Selain menghitung FPB, alat ini menyediakan tabel pembagian langkah-demi-langkah yang sepenuhnya dianimasikan, substitusi balik, dan perhitungan invers modular, menjadikannya ideal untuk kursus teori bilangan, studi kriptografi, dan pemrograman kompetitif.

Apa itu Algoritma Euklides Diperluas?

Algoritma Euklides Diperluas (EEA) adalah pengembangan dari algoritma FPB klasik Euklides. Sementara algoritma dasar menemukan fpb(a, b) melalui pembagian berulang, versi yang diperluas secara bersamaan melacak dua urutan bilangan bulat yang mencatat bagaimana setiap sisa dapat dinyatakan sebagai kombinasi linier dari input aslinya.

Cara Kerja Algoritma

EEA mempertahankan tiga pasang nilai — (r, s, t) — melalui setiap langkah pembagian:

1. Inisialisasi: r₀ = |a|, r₁ = |b|, s₀ = 1, s₁ = 0, t₀ = 0, t₁ = 1
2. Setiap langkah: hitung hasil bagi q = ⌊rₙ₋₁ / rₙ⌋, lalu perbarui rₙ₊₁ = rₙ₋₁ − q·rₙ, sₙ₊₁ = sₙ₋₁ − q·sₙ, tₙ₊₁ = tₙ₋₁ − q·tₙ
3. Berhenti ketika sisa pembagian = 0; sisa pembagian sebelumnya adalah fpb(a, b)
4. Nilai s dan t yang sesuai adalah koefisien Bézout

Contoh Langkah-demi-Langkah: fpb(252, 105)

Hasil: fpb(252, 105) = 21, dengan identitas Bézout: 21 = (−2) × 252 + 5 × 105 (s = −2, t = 5). Coba sendiri dengan kalkulator di atas untuk mendapatkan koefisien yang tepat.

Aplikasi Algoritma Euklides Diperluas

1. Invers Modular (Kriptografi)

Aplikasi yang paling penting adalah menghitung invers modular. Jika fpb(a, m) = 1, maka koefisien Bézout s memenuhi:

Invers modular sangat penting dalam enkripsi RSA (menghitung eksponen kunci pribadi d), pertukaran kunci Diffie-Hellman, dan kriptografi kurva eliptik.

2. Menyelesaikan Persamaan Diophantine Linier

Persamaan ax + by = c memiliki solusi bilangan bulat jika dan hanya jika fpb(a, b) membagi c. Jika demikian, solusi khususnya adalah x₀ = s·(c/d), y₀ = t·(c/d) di mana d = fpb(a, b) dan s, t adalah koefisien Bézout.

3. Teorema Sisa Tiongkok (Chinese Remainder Theorem)

EEA digunakan dalam pembuktian konstruktif dan perhitungan Teorema Sisa Tiongkok — menemukan x sedemikian hingga x ≡ a₁ (mod m₁) dan x ≡ a₂ (mod m₂) — dengan menghitung invers modular dari moduli.

4. Penyederhanaan Pecahan dan KPK

fpb(a, b) = 1 memastikan bahwa a/b sudah dalam bentuk yang paling sederhana. KPK adalah kpk(a, b) = |a·b| / fpb(a, b).

Koefisien Bézout Tidak Unik

Koefisien Bézout s dan t tidak unik. Jika (s, t) adalah salah satu solusi, maka (s + k·(b/d), t − k·(a/d)) juga merupakan solusi untuk setiap bilangan bulat k, di mana d = fpb(a, b). EEA mengembalikan solusi di mana |s| ≤ |b/d| dan |t| ≤ |a/d|.

Kompleksitas Waktu

Algoritma Euklides Diperluas berjalan dalam iterasi O(log min(a, b)) — sama dengan algoritma Euklides dasar. Berdasarkan teorema Lamé, jumlah langkah tidak pernah melebihi 5 kali jumlah digit desimal dari input yang lebih kecil. Hal ini membuatnya sangat efisien bahkan untuk bilangan bulat besar yang digunakan dalam aplikasi kriptografi.

Pertanyaan yang Sering Diajukan

Apa itu Algoritma Euklides Diperluas?

Algoritma Euklides Diperluas memperluas algoritma FPB Euklides untuk juga menghitung koefisien Bézout s dan t yang memenuhi fpb(a, b) = s·a + t·b. Algoritma ini melacak bagaimana setiap sisa dapat dinyatakan sebagai kombinasi linier dari a dan b selama proses pembagian.

Apa itu koefisien Bézout?

Koefisien Bézout adalah bilangan bulat s dan t yang dijamin ada oleh identitas Bézout (sebuah teorema dalam teori bilangan). Koefisien ini memenuhi fpb(a, b) = s·a + t·b dan dihitung secara efisien oleh Algoritma Euklides Diperluas. Koefisien ini digunakan dalam perhitungan invers modular, penyelesaian persamaan Diophantine, dan Teorema Sisa Tiongkok.

Bagaimana cara mencari invers modular menggunakan Algoritma Euklides Diperluas?

Jika fpb(a, b) = 1 (a dan b adalah koprima), koefisien Bézout s memenuhi s·a ≡ 1 (mod b). Invers modular dari a mod b adalah s mod b (disesuaikan agar menjadi positif). Kalkulator ini menampilkan hasil tersebut secara langsung.

Kapan invers modular tidak ada?

Invers modular dari a modulo m ada jika dan hanya jika fpb(a, m) = 1. Jika fpb(a, m) > 1, tidak ada bilangan bulat x yang memenuhi a·x ≡ 1 (mod m).

Berapa kompleksitas waktu dari Algoritma Euklides Diperluas?

O(log min(a, b)) pembagian, sama seperti algoritma Euklides dasar. Menurut teorema Lamé, jumlah langkah dibatasi oleh 5 kali jumlah digit desimal dari input yang lebih kecil, menjadikannya sangat efisien.

Sumber Tambahan

• Algoritma Euklides Diperluas - Wikipedia
• Identitas Bézout - Wikipedia
• Invers Perkalian Modular - Wikipedia