Apakah BGP & GPM?
Pembahagi Bersama Terbesar (GCD) dan Gandaan Bersama Terkecil (LCM) adalah dua konsep terpenting dalam teori nombor asas, dengan aplikasi daripada penymbangan pecahan di sekolah menengah kepada algoritma kriptografi yang memastikan keselamatan internet.
Algoritma Euclidean, yang diterangkan oleh Euclid sekitar 300 SM, adalah salah satu algoritma tertua dan paling cekap dalam matematik. Ia mengira GCD dalam O(log(min(a,b))) langkah, berhenti dengan cepat walaupun untuk nombor yang sangat besar. Algoritma menggunakan identiti: GCD(a, b) = GCD(b, a mod b) berulang kali sehingga baki ialah sifar.
Kalkulator ini menunjukkan algoritma Euclidean lengkap langkah demi langkah untuk dua nombor, dan juga mengira GCD dan LCM untuk senarai berbilang nombor menggunakan penggeneralisasian: GCD(a, b, c) = GCD(GCD(a, b), c).
Bila Menggunakan Kalkulator Ini
- Untuk mengecilkan pecahan.
- Dalam masalah jadual berulang.
- Dalam enkripsi data.
- Untuk mencari penyebut persekutuan terkecil.
- Dalam masalah geometri.
- Dalam pengkomputeran.
Langkah:
- Masukkan dua integer positif a dan b.
- Gunakan bahagian integer: a = q×b + r.
- Gantikan a dengan b dan b dengan r. Ulang sehingga r = 0.
- Baki bukan sifar terakhir ialah GCD.
- Kira LCM = |a × b| / GCD menggunakan identiti asas.
- Gunakan mod Nombor Berbilang untuk tiga nombor atau lebih.
Rumus
Algoritma Euclidean:
GCD(a, b) = GCD(b, a mod b) sehingga b = 0
LCM daripada GCD:
LCM(a, b) = |a × b| / GCD(a, b)
Untuk berbilang nombor:
GCD(a, b, c) = GCD(GCD(a, b), c)
LCM(a, b, c) = LCM(LCM(a, b), c)
Kes Penggunaan
- Menyimbang pecahan: ringkaskan a/b dengan membahagikan kedua-duanya dengan GCD(a, b)
- Menambah pecahan dengan penyebut berbeza: cari LCM penyebut
- Penjadualan: mencari bila dua peristiwa berulang akan bertemu seterusnya
- Penjanaan kunci RSA: menyemak bahawa eksponen e adalah sederhana dengan φ(n)
- Masalah nisbah gear dalam kejuruteraan mekanikal
- Reka bentuk corak jubin: mencari unit berulang terkecil
Faedah Utama
- Membantu mengecilkan pecahan.
- Digunakan dalam enkripsi RSA.
- Membantu menyelesaikan masalah jadual berulang.
- Digunakan untuk mencari penyebut persekutuan terkecil.
- Berguna dalam pengkomputeran.
- Membantu memahami sifat nombor perdana.
Tips Pro
- Gunakan Algoritma Euclidean untuk nombor besar.
- Ingat GCD(a, b) = GCD(b, a mod b).
- Sahkan dengan GCD × LCM = a × b.
- GCD(0, a) = a untuk setiap positif a.
- Bahagi numerator dan penyebut dengan FPB.
- Untuk beberapa nombor, kira KPK secara berurutan.
Kesilapan Biasa
- Menganggap GCD(0, 0) = 0.
- Mencampuradukkan FPB dan KPK.
- Lupa bahawa FPB menggunakan nilai mutlak.
- Mencuba mengira FPB tanpa algoritma yang jelas.
- Menganggap FPB selalu lebih besar daripada KPK.
- Lupa mengesahkan GCD × LCM = a × b.
Istilah Utama
- GCD: Integer terbesar yang membahagikan kedua-dua nombor tanpa baki
- LCM: Integer positif terkecil yang boleh dibahagikan oleh kedua-dua nombor
- Nombor sederhana: Dua nombor dengan GCD = 1, tidak berkongsi sebarang faktor perdana biasa
- Algoritma Euclidean: Algoritma purba yang mengira GCD melalui bahagian berulang
- Operasi modulo: a mod b ialah baki apabila a dibahagi oleh b
- Kecacatan bahagi: a membahagi b jika b/a tiada baki
Konsep Berkaitan
- Algoritma Euclidean: Algoritma cekap untuk mengira FPB.
- Pengambungan Perdana: Penguraian nombor kepada faktor perdana.
- Nombor Coprime: Nombor dengan GCD = 1.
- Faktor Persekutuan: Nombor yang membahagi kedua-duanya.
- Kelipatan Persekutuan: Nombor dalam jadual pendaraban kedua-duanya.
Contoh
Cari GCD(48, 18): 48 = 2×18 + 12 → 18 = 1×12 + 6 → 12 = 2×6 + 0. GCD = 6. LCM = |48×18|/6 = 864/6 = 144. Semak: 144/48 = 3 ✓, 144/18 = 8 ✓.
Mentafsir Hasil
FPB ialah faktor persekutuan terbesar, KPK ialah kelipatan persekutuan terkecil. Jika GCD = 1, nombor adalah coprime.