guest@itl:~/home/algebra$
templates/gcd-lcm-extended-gcd.cpp
compilable
$cat templates/gcd-lcm-extended-gcd

GCD, LCM & Extended GCD

GCD, LCM, Extended Euclidean algorithm, and linear Diophantine equation solver.

[Algebra]|
Jul 9, 2026
|explanatory_notes.md|
#gcd#lcm#extended-gcd#diophantine#bezout
Log in to track progress, save custom versions, and organize into collections.Log In
$cat source_code/
cpp
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

ll gcd(ll a, ll b) {
  while (b) {
    a %= b;
    swap(a, b);
  }
  return a;
}

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

ll extgcd(ll a, ll b, ll& x, ll& y) {
  if (!b) {
    x = 1;
    y = 0;
    return a;
  }
  ll x1, y1;
  ll g = extgcd(b, a % b, x1, y1);
  x = y1;
  y = x1 - (a / b) * y1;
  return g;
}

bool solveLinear(ll a, ll b, ll c, ll& x0, ll& y0, ll& g) {
  g = extgcd(abs(a), abs(b), x0, y0);
  if (c % g) return false;
  x0 *= c / g;
  y0 *= c / g;
  if (a < 0) x0 = -x0;
  if (b < 0) y0 = -y0;
  return true;
}
36 linesutf-8
$cat explanation_notes.md
notes_viewer --renderedmarkdown (math enabled)

GCD, LCM & Extended GCD

Functions

  • gcd(a, b) — Euclidean algorithm: replace (a,b)(a, b) with (b,a mod b)(b, a \bmod b) until b=0b = 0

  • lcm(a, b) — lcm(a,b)=agcd⁡(a,b)⋅b\text{lcm}(a, b) = \frac{a}{\gcd(a,b)} \cdot b (divide first to avoid overflow)

  • extgcd(a, b, x, y) — finds x,yx, y such that ax+by=gcd⁡(a,b)ax + by = \gcd(a, b) (Bezout's identity)

  • solveLinear(a, b, c, x0, y0, g) — solves ax+by=cax + by = c. Solution exists iff gcd⁡(a,b)∣c\gcd(a,b) \mid c

    • General Solution for ax+by=cax + by = c

    Given one solution (x0,y0)(x_0, y_0), all solutions:

    x=x0+bg⋅t,y=y0−ag⋅tx = x_0 + \frac{b}{g} \cdot t, \quad y = y_0 - \frac{a}{g} \cdot t

    for any integer tt.

    When to Use

  • Fraction simplification, divisibility checks

  • Modular inverse when mod isn't prime

  • Solving Diophantine equations, CRT steps

    • Complexity

  • All functions — O(log⁡min⁡(a,b))O(\log \min(a, b))