Kalkulator LCM & GCD

FST ialah integer positif terbesar yang membahagikan semua nombor yang diberikan tanpa baki.

Gunakan algoritma Euclid untuk pengiraan yang cekap: bahagi dan ambil baki secara berulang sehingga anda mendapat 0.

KSM ialah integer positif terkecil yang boleh dibahagi dengan semua nombor yang diberikan.

Kira menggunakan faktoran perdana (ambil kuasa tertinggi) atau formula: KSM = (a × b) / FST.

FST (faktor sepunya terbesar) ialah integer terbesar yang membahagikan setiap nombor yang diberikan tepat, manakala KSM (gandaan sepunya terkecil) ialah integer positif terkecil yang boleh dibahagi tepat oleh setiap nombor yang diberikan.

Keduanyak bertindak bertentangan arah: FST melihat ke bawah kepada faktor berkongsi terbesar, manakala KSM melihat ke atas kepada gandaan berkongsi terkecil. Bagi 12 dan 18, FST ialah 6 dan KSM ialah 36.

Menurut Wolfram MathWorld, FST juga ditulis sebagai gcd(a, b) atau (a, b), dan istilah "faktor sepunya tertinggi" (HCF) ialah sinonim bahasa Inggeris British yang biasa digunakan untuk kuantiti yang sama.

Algoritma Euclid mencari FST (faktor sepunya terbesar) dengan menggantikan nombor yang lebih besar berulang kali dengan baki pembahagiannya dengan nombor yang lebih kecil, dan berhenti apabila baki mencecah sifar; baki bukan sifar yang terakhir ialah FST.

Bagi 48 dan 18: 48 = 2×18 + 12, kemudian 18 = 1×12 + 6, kemudian 12 = 2×6 + 0, jadi fst(48, 18) = 6.

Encyclopaedia Britannica menyatakan kaedah ini bermula sejak Elemen Euclid (sekitar 300 BCE), menjadikannya salah satu algoritma tertua yang masih digunakan setiap hari. Kecekapannya adalah sebab perpustakaan perisian menggunakannya berbanding memfaktorkan nombor yang besar.

Untuk mencari GST melalui pemfaktoran perdana, faktorkan setiap nombor kepada nombor perdana, kemudian darabkan setiap nombor perdana yang dinaikkan kepada kuasa tertingginya yang muncul dalam mana-mana pemfaktoran.

Bagi 12 = 2²×3 dan 18 = 2×3², ambil 2² dan 3², memberikan GST = 4×9 = 36. Untuk FST pula, ambil setiap nombor perdana sepunya pada kuasa terendahnya: 2¹×3¹ = 6.

Khan Academy mengajar perbandingan bersebelahan ini kerana ia menjadikan kontras GST/FST berbentuk visual. Pemfaktoran perdana adalah mudah difahami untuk nombor kecil tetapi lebih perlahan berbanding algoritma Euclid untuk nombor besar, memandangkan pemfaktoran adalah sukar dari segi pengkomputeran.

Bagi mana-mana dua integer positif a dan b, GST(a, b) × FST(a, b) = a × b. Identiti ini membolehkan anda mengira satu kuantiti daripada yang satu lagi: GST(a, b) = (a × b) / FST(a, b).

Bagi 12 dan 18, FST ialah 6, jadi GST = (12 × 18) / 6 = 216 / 6 = 36, dan sememangnya 6 × 36 = 216 = 12 × 18.

Wolfram MathWorld mendokumentasikan hubungan ini sebagai jambatan standard antara kedua-dua fungsi tersebut. Ambil perhatian bahawa formula ini hanya terpakai untuk dua nombor; untuk tiga atau lebih, anda menggunakannya secara berpasangan dan bukannya menganggap hasil darab bersamaan dengan GST × FST.

Untuk tiga nombor atau lebih, gunakan FST atau GST secara berpasangan: kira hasil daripada dua yang pertama, kemudian gabungkan hasilnya dengan nombor seterusnya, dan begitu seterusnya.

Sebagai contoh, fst(12, 18, 24) = fst(fst(12, 18), 24) = fst(6, 24) = 6, dan gst(4, 6, 8) = gst(gst(4, 6), 8) = gst(12, 8) = 24. Kedua-dua operasi ini bersifat bersekutu, jadi susunan pengumpulan tidak mengubah jawapan.

Kalkulator ini mengendalikan kelompok secara automatik, tetapi jalan pintas GST×FST = hasil darab tidak boleh dilanjutkan kepada tiga input atau lebih, satu perkara yang ditekankan oleh Wolfram MathWorld.

Dua nombor dikatakan saling perdana (coprime) apabila FST mereka sama dengan 1, bermaksud mereka tidak berkongsi sebarang faktor perdana walaupun tiada satu pun daripadanya merupakan nombor perdana.

Sebagai contoh, fst(8, 15) = 1: 8 = 2³ dan 15 = 3×5 tidak mempunyai nombor perdana sepunya, jadi ia adalah saling perdana. Apabila nombor-nombor adalah saling perdana, GST mereka adalah bersamaan dengan hasil darabnya; gst(8, 15) = 120 = 8×15.

Wolfram MathWorld menyatakan bahawa kekongsian perdana mendasari aritmetik modular dan kriptografi RSA, di mana penjanaan kunci memerlukan eksponen yang saling perdana dengan totient Euler. Sifat saling perdana adalah ciri bagi satu pasangan, bukannya untuk nombor individu.

GST dan FST muncul jauh melangkaui buku teks.

FST memudahkan pecahan kepada sebutan terendah (12/18 dikurangkan kepada 2/3 selepas dibahagikan dengan 6) dan mencari kumpulan saiz sama yang terbesar apabila mengedarkan item — dan sebaik sahaja kumpulan tersebut ditetapkan, kalkulator faktorial mengira cara untuk menyusun item dalam setiap kumpulan.

GST mencari masa apabila peristiwa berulang bertindih, seperti dua bas bertolak setiap 12 dan 18 minit bertemu semula selepas 36 minit, dan ia menghasilkan penyebut sepunya untuk menjumlahkan pecahan.

Jurutera menggunakan FST dalam reka bentuk nisbah gear dan tali sawat pemasa, manakala pakar kriptografi bergantung pada semakan saling perdana (FST = 1) semasa tetapan kunci RSA, seperti yang diterangkan oleh Encyclopaedia Britannica dalam liputannya mengenai aplikasi teori nombor.

Identiti Bézout menyatakan bahawa bagi integer a dan b, wujud integer x dan y sedemikian rupa sehingga ax + by = fst(a, b).

Bagi 12 dan 18, FST ialah 6, dan satu penyelesaian ialah 12×(−1) + 18×(1) = −12 + 18 = 6. Algoritma Euclid lanjutan mengira pekali ini semasa ia mengira FST, yang merupakan cara tepat untuk mencari songsangan modular dalam kriptografi.

Wolfram MathWorld dan NIST Digital Library of Mathematical Functions kedua-duanya menganggap identiti Bézout sebagai hasil asas teori nombor permulaan, kerana ia menjamin kewujudan gabungan linear yang sama dengan FST.

Beberapa kesilapan lazim sering menjerat orang ramai apabila mengira GST dan FST:

• Ralat yang kerap berlaku ialah tertukar antara kedua-duanya: FST tidak pernah lebih besar daripada input terkecil, manakala GST tidak pernah lebih kecil daripada input terbesar, jadi semak jawapan anda berdasarkan had tersebut.

• Satu lagi kesilapan ialah menganggap GST × FST = hasil darab berfungsi untuk tiga nombor atau lebih, padahal ia tidak.

• Orang ramai juga lupa bahawa FST dan GST adalah ditetapkan untuk integer positif, bukan pecahan atau perpuluhan, jadi input mestilah nombor bulat.

• Akhir sekali, apabila nombor adalah saling perdana, ingat bahawa FST ialah 1 (bukan 0), dan GST adalah bersamaan dengan hasil darabnya.

Memverifikasi dengan identiti GST×FST = a×b dapat mengesan kebanyakan kesilapan pengiraan dua nombor.