GCD dan LCM

GCD (Greatest Common Divisor, FPB) dan LCM (Least Common Multiple, KPK) adalah operasi fundamental dalam teori bilangan yang muncul di banyak algoritma — dari penyederhanaan pecahan, perhitungan periode, hingga penyelesaian sistem kongruensi (Chinese Remainder Theorem). Pada Chapter ini kita akan menurunkan algoritma Euclidean untuk GCD, melihat relasi lcm(a,b) = a·b/gcd(a,b), dan memakai utilitas standar C++ std::gcd/std::lcm.

Definisi dan Relasi #

Aturan #

GCD(a, b): bilangan bulat positif terbesar yang membagi habis a dan b. Secara formal, gcd(a, b) = max{d : d | a ∧ d | b}.
LCM(a, b): bilangan bulat positif terkecil yang merupakan kelipatan a dan b. Secara formal, lcm(a, b) = min{m > 0 : a | m ∧ b | m}.
Relasi: gcd(a, b) · lcm(a, b) = |a · b|.

Mekanisme: Mengapa Relasi Berlaku #

Tulis a = g · a' dan b = g · b' dengan g = gcd(a, b) sehingga gcd(a', b') = 1. Maka lcm(a, b) = g · a' · b' (perlu kedua faktor prima dari a dan b, tetapi a' dan b' coprime jadi tidak ada duplikasi). Maka gcd · lcm = g · (g · a' · b') = g² · a' · b' = (g · a') · (g · b') = a · b. Sesuai.

Algoritma Euclidean #

Aturan #

Algoritma Euclidean menggunakan relasi rekursif:

text

gcd(a, 0) = a
gcd(a, b) = gcd(b, a mod b)         bila b > 0

Setiap iterasi mengecilkan bilangan — b diganti dengan a mod b yang lebih kecil. Setelah ~log₂(b) iterasi, salah satu bilangan menjadi 0 dan yang lainnya adalah GCD.

Mekanisme: Kenapa `gcd(b, a mod b)` Benar #

Misalkan d pembagi bersama a dan b. Maka d | a dan d | b, sehingga d | (a - k·b) untuk sembarang k. Khususnya d | (a mod b) = a - floor(a/b) · b. Jadi d juga pembagi b dan a mod b. Sebaliknya, pembagi b dan a mod b juga membagi a = b · floor(a/b) + (a mod b). Maka himpunan pembagi (a, b) = himpunan pembagi (b, a mod b). GCD-nya sama.

Kode: Euclidean Rekursif #

cpp
#include <iostream>

long long gcd(long long a, long long b) {
    if (b == 0) return a;
    return gcd(b, a % b);
}

int main() {
    std::cout << "gcd(48, 18) = " << gcd(48, 18) << '\n';
    std::cout << "gcd(100, 75) = " << gcd(100, 75) << '\n';
    std::cout << "gcd(17, 5) = " << gcd(17, 5) << '\n';
    std::cout << "gcd(0, 5) = " << gcd(0, 5) << '\n';
    std::cout << "gcd(5, 0) = " << gcd(5, 0) << '\n';
    std::cout << "gcd(1000000000, 999999999) = "
              << gcd(1'000'000'000LL, 999'999'999LL) << '\n';
    return 0;
}

Output yang Dihasilkan:

text
gcd(48, 18) = 6
gcd(100, 75) = 25
gcd(17, 5) = 1
gcd(0, 5) = 5
gcd(5, 0) = 5
gcd(1000000000, 999999999) = 1

Baris if (b == 0) return a;: base case. Bila b = 0, GCD adalah a (yang lain nol — apa pun adalah pembagi 0).
Baris return gcd(b, a % b);: rekursif. Parameter pertama menjadi b lama, parameter kedua menjadi sisa a mod b.
Hasil gcd(48, 18) = 6: faktor 48 = 2⁴ · 3, 18 = 2 · 3². FPB = 2 · 3 = 6. Sesuai.
Hasil gcd(17, 5) = 1: 17 prima, 5 prima, tidak ada pembagi bersama selain 1 → coprime.
Hasil gcd(0, 5) = 5: kasus khusus — gcd(0, x) = x untuk x > 0.
Hasil gcd(10^9, 999'999'999) = 1: dua bilangan berdekatan bisa coprime. 10⁹ = 2⁹ · 5⁹, 999'999'999 = 3⁴ · 37 · 333667. Tidak ada faktor persekutuan.

Iteratif (Lebih Cepat, Tanpa Stack) #

Aturan #

Versi rekursif dapat overflow stack untuk iterasi sangat banyak (jarang terjadi, tetapi mungkin). Versi iteratif lebih aman dan sedikit lebih cepat.

Kode: Euclidean Iteratif #

cpp
#include <iostream>

long long gcd_iter(long long a, long long b) {
    while (b != 0) {
        long long t = b;
        b = a % b;
        a = t;
    }
    return a;
}

int main() {
    std::cout << "gcd_iter(48, 18) = " << gcd_iter(48, 18) << '\n';
    std::cout << "gcd_iter(123456789012LL, 987654321098LL) = "
              << gcd_iter(123456789012LL, 987654321098LL) << '\n';
    return 0;
}

Output yang Dihasilkan:

text

gcd_iter(48, 18) = 6
gcd_iter(123456789012, 987654321098) = 2

Baris long long t = b;: simpan b sementara sebelum di-overwrite.
Baris b = a % b;: ganti b dengan sisa a mod b.
Baris a = t;: ganti a dengan b lama (yang disimpan di t).
Hasil gcd(123456789012, 987654321098) = 2: kedua bilangan genap, sehingga minimal GCD = 2.

LCM dan Jebakan Overflow #

Aturan #

Formula lcm(a, b) = a · b / gcd(a, b) mudah, tetapi a · b bisa overflow sebelum dibagi. Solusi: bagi dulu, lalu kali.

Kode: LCM yang Aman #

cpp
#include <iostream>

long long gcd(long long a, long long b) {
    while (b != 0) { long long t = b; b = a % b; a = t; }
    return a;
}

long long lcm(long long a, long long b) {
    if (a == 0 || b == 0) return 0;
    return (a / gcd(a, b)) * b;  // bagi dulu, baru kali
}

int main() {
    std::cout << "lcm(4, 6) = " << lcm(4, 6) << '\n';
    std::cout << "lcm(12, 18) = " << lcm(12, 18) << '\n';
    std::cout << "lcm(7, 11) = " << lcm(7, 11) << '\n';
    // Demonstrasi: tanpa bagi-dulu, akan overflow
    long long a = 1'000'000'000LL;
    long long b = 999'999'999LL;
    std::cout << "lcm(10^9, 10^9-1) = " << lcm(a, b) << '\n';
    std::cout << "(10^9 * (10^9-1)) overflow? "
              << (a * b > 0 ? "tidak overflow" : "overflow") << '\n';
    return 0;
}

Output yang Dihasilkan:

text
lcm(4, 6) = 12
lcm(12, 18) = 36
lcm(7, 11) = 77
lcm(10^9, 10^9-1) = 999999999000000000
(10^9 * (10^9-1)) overflow? tidak overflow

Baris if (a == 0 || b == 0) return 0;: kasus khusus — LCM dengan nol adalah 0 (0 adalah kelipatan persekutuan terkecil).
Baris return (a / gcd(a, b)) * b;: bagi dulu a dengan gcd(a,b) (yang habis membagi a), baru kali dengan b. Hasil a/gcd lebih kecil, sehingga perkaliannya dengan b tidak overflow.
Hasil lcm(4, 6) = 12: 12 = 4·6/2 = 12. Sesuai.
Hasil lcm(7, 11) = 77: 7 dan 11 coprime, LCM = 7·11 = 77.
Hasil lcm(10^9, 10^9-1) = 999999999000000000: kedua bilangan coprime (10⁹ = 2⁹·5⁹, 10⁹-1 = 3²·37·333667·9·1… eh). LCM = a·b karena coprime = 10⁹·(10⁹-1) ≈ 10¹⁸. Masih muat di long long.
Hasil “tidak overflow”: a*b = 10⁹·(10⁹-1) ≈ 10¹⁸ < 1.8·10¹⁹ = max long long. Tidak overflow di sini, tetapi bila a dan b mendekati max long long, perkalian langsung pasti overflow.

std::gcd dan std::lcm (C++17) #

Aturan #

C++17 menyediakan std::gcd dan std::lcm di <numeric>. Implementasi standar, efisien, dan teruji.

Kode: Pakai std::gcd #

cpp
#include <iostream>
#include <numeric>

int main() {
    std::cout << "std::gcd(48, 18) = " << std::gcd(48LL, 18LL) << '\n';
    std::cout << "std::gcd(100, 75) = " << std::gcd(100LL, 75LL) << '\n';
    std::cout << "std::lcm(4, 6) = " << std::lcm(4LL, 6LL) << '\n';
    std::cout << "std::lcm(12, 18) = " << std::lcm(12LL, 18LL) << '\n';
    return 0;
}

Output yang Dihasilkan:

text
std::gcd(48, 18) = 6
std::gcd(100, 75) = 25
std::lcm(4, 6) = 12
std::lcm(12, 18) = 36

Baris #include <numeric>: header yang berisi std::gcd dan std::lcm sejak C++17.
Baris std::gcd(48LL, 18LL): panggil dengan tipe eksplisit long long untuk menghindari konversi implisit.
Hasil identik dengan implementasi manual — std::gcd menggunakan algoritma Euclidean yang sama, tetapi dioptimalkan oleh implementasi compiler.

Aplikasi: Sistem Kongruensi via CRT #

Aturan #

Chinese Remainder Theorem (CRT): bila m_1, m_2, ..., m_k saling coprime, sistem kongruensi x ≡ a_i (mod m_i) memiliki solusi unik modulo M = m_1 · m_2 · ... · m_k. Implementasi membutuhkan GCD dan modular inverse.

Ringkasan #

GCD via Euclidean: gcd(a, 0) = a, gcd(a, b) = gcd(b, a mod b). Kompleksitas O(log min(a, b)).
LCM: lcm(a, b) = a · b / gcd(a, b). Bagi dulu untuk menghindari overflow: (a / gcd) * b.
C++17 menyediakan std::gcd dan std::lcm di <numeric>. Selalu pakai untuk kode produksi.
Aplikasi: penyederhanaan pecahan, CRT, modular inverse, periode siklik, penyelesaian Diophantine.

Definisi dan Relasi #

Aturan #

Mekanisme: Mengapa Relasi Berlaku #

Algoritma Euclidean #

Aturan #

Mekanisme: Kenapa gcd(b, a mod b) Benar #

Kode: Euclidean Rekursif #

Iteratif (Lebih Cepat, Tanpa Stack) #

Aturan #

Kode: Euclidean Iteratif #

LCM dan Jebakan Overflow #

Aturan #

Kode: LCM yang Aman #

std::gcd dan std::lcm (C++17) #

Aturan #

Kode: Pakai std::gcd #

Aplikasi: Sistem Kongruensi via CRT #

Aturan #

Ringkasan #

Mekanisme: Kenapa `gcd(b, a mod b)` Benar #