GCD, LCM, and Extended Euclidean Algorithm

#include <stdio.h>

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

long long lcm(long long a, long long b) {
    return a / gcd(a, b) * b;  // divide first to avoid overflow
}

// Extended Euclidean: finds x, y such that ax + by = gcd(a, b)
long long extgcd(long long a, long long b, long long *x, long long *y) {
    if (b == 0) { *x = 1; *y = 0; return a; }
    long long x1, y1;
    long long g = extgcd(b, a % b, &x1, &y1);
    *x = y1;
    *y = x1 - (a / b) * y1;
    return g;
}

int main() {
    printf("gcd(48, 18) = %lld\n", gcd(48, 18));  // 6
    printf("lcm(4, 6) = %lld\n", lcm(4, 6));      // 12
    return 0;
}

#include <bits/stdc++.h>
using namespace std;

long long gcd(long long a, long long b) {
    return b ? gcd(b, a % b) : a;
}

long long lcm(long long a, long long b) {
    return a / gcd(a, b) * b;
}

// Modular inverse using extended GCD
long long modInverse(long long a, long long m) {
    long long g, x, y;
    // extended gcd
    function<long long(long long, long long, long long&, long long&)> ext =
        [&](long long a, long long b, long long& x, long long& y) -> long long {
            if (!b) { x = 1; y = 0; return a; }
            long long x1, y1;
            long long g = ext(b, a % b, x1, y1);
            x = y1; y = x1 - (a / b) * y1;
            return g;
        };
    g = ext(a, m, x, y);
    if (g != 1) return -1; // no inverse
    return (x % m + m) % m;
}

public class GCDUtils {
    public static long gcd(long a, long b) {
        return b == 0 ? a : gcd(b, a % b);
    }

    public static long lcm(long a, long b) {
        return a / gcd(a, b) * b;
    }

    // Returns {gcd, x, y} such that a*x + b*y = gcd
    public static long[] extGcd(long a, long b) {
        if (b == 0) return new long[]{a, 1, 0};
        long[] r = extGcd(b, a % b);
        return new long[]{r[0], r[2], r[1] - (a / b) * r[2]};
    }

    public static long modInverse(long a, long m) {
        long[] r = extGcd(a, m);
        if (r[0] != 1) return -1;
        return (r[1] % m + m) % m;
    }
}

function gcd(a, b) {
    return b === 0 ? a : gcd(b, a % b);
}

function lcm(a, b) {
    return (a / gcd(a, b)) * b;
}

function extGcd(a, b) {
    if (b === 0) return [a, 1, 0];
    const [g, x, y] = extGcd(b, a % b);
    return [g, y, x - Math.floor(a / b) * y];
}

function modInverse(a, m) {
    const [g, x] = extGcd(a, m);
    if (g !== 1) return -1;
    return ((x % m) + m) % m;
}

from math import gcd

def lcm(a, b):
    return a // gcd(a, b) * b

def ext_gcd(a, b):
    if b == 0:
        return a, 1, 0
    g, x, y = ext_gcd(b, a % b)
    return g, y, x - (a // b) * y

def mod_inverse(a, m):
    g, x, _ = ext_gcd(a, m)
    if g != 1:
        return -1  # no inverse exists
    return x % m

# Fermat's little theorem (when m is prime): a^(m-2) mod m
def mod_inverse_prime(a, m):
    return pow(a, m - 2, m)