{"title":"GCD and LCM","description":"","content":"GCD (Greatest Common Divisor) and LCM (Least Common Multiple) are simple concepts that are often used in questions involving divisibility, fractions, ratios, and number relationships.\n\nThey underpin solutions in problems about simplifying fractions, detecting cycles, periodic patterns, and divisibility constraints. The rest of this chapter covers their definitions, the Euclidean algorithm, the Extended Euclidean variant, and modular inverse as one of its main applications.\n\n---\n\n# Core Concept: GCD and LCM Defined\n\n### Greatest Common Divisor (GCD)\n\nThe GCD of two integers `a` and `b` is the largest positive integer that divides both `a` and `b` without leaving a remainder.\n\nFor example:\n\n- gcd(12, 18) = 6, because 6 is the largest number that divides both 12 and 18.\n- gcd(7, 13) = 1, because 7 and 13 share no common factor other than 1 (they are coprime).\n- gcd(0, 5) = 5, because every integer divides 0.\n\n### Least Common Multiple (LCM)\n\nThe LCM of two integers `a` and `b` is the smallest positive integer that is a multiple of both `a` and `b`.\n\nFor example:\n\n- lcm(12, 18) = 36\n- lcm(4, 6) = 12\n- lcm(7, 13) = 91\n\nThe key relationship between GCD and LCM is:\n\n\n```shell\nlcm(a, b) = (a * b) / gcd(a, b)\n```\n\n\nThis means once you can compute GCD efficiently, LCM comes for free.\n\n---\n\n# The Euclidean Algorithm\n\nThe naive way to find GCD is to list all divisors of both numbers and pick the largest common one. That works, but it is slow. The Euclidean algorithm is dramatically faster, and the idea is elegant.\n\n### The Key Insight\n\nThe Euclidean algorithm is based on one simple observation:\n\n\n```shell\ngcd(a, b) = gcd(b, a % b)\n```\n\n\nIn words: the GCD of two numbers is the same as the GCD of the smaller number and the remainder when you divide the larger by the smaller. You keep reducing until the remainder hits zero, at which point the other number is the GCD.\n\n### Why Does This Work?\n\nHere is the intuition. Suppose `d` divides both `a` and `b`. Then `a = d * p` and `b = d * q` for some integers `p` and `q`. The remainder `a % b = a - k * b` for some integer `k`, which equals `d * p - k * d * q = d * (p - k*q)`. So `d` also divides the remainder. This means every common divisor of `a` and `b` is also a common divisor of `b` and `a % b`. The argument works in reverse too, so the two pairs have exactly the same set of common divisors, and therefore the same GCD.\n\nLet us trace gcd(48, 18) through the Euclidean algorithm:\n\n\n```mermaid\nflowchart LR\n A[\"gcd(48, 18)\"]:::primary --> B[\"48 % 18 = 12\"]:::orange\n B --> C[\"gcd(18, 12)\"]:::primary\n C --> D[\"18 % 12 = 6\"]:::orange\n D --> E[\"gcd(12, 6)\"]:::primary\n E --> F[\"12 % 6 = 0\"]:::orange\n F --> G[\"gcd(6, 0) = 6\"]:::green\n\n classDef primary fill:#00ceff,stroke:#000,color:#000\n classDef orange fill:#ffa94d,stroke:#000,color:#000\n classDef green fill:#69db7c,stroke:#000,color:#000\n```\n\n\nEach step replaces the larger number with the remainder, shrinking the problem until it vanishes. When the remainder is 0, the answer is the non-zero value.\n\n---\n\n# Extended Euclidean Algorithm\n\nThe standard Euclidean algorithm finds gcd(a, b). The **extended** version goes further: it finds integers `x` and `y` such that:\n\n\n```shell\na * x + b * y = gcd(a, b)\n```\n\n\nThis is known as **Bezout's Identity**, and it guarantees that such `x` and `y` always exist.\n\nWhy is this useful? The extended GCD is the backbone of:\n\n- **Modular inverse:** Finding `x` such that `a * x ≡ 1 (mod m)`, which requires solving `a * x + m * y = 1`.\n- **Solving linear Diophantine equations:** Equations of the form `ax + by = c` have integer solutions if and only if `gcd(a, b)` divides `c`.\n\nThe algorithm works by tracking the coefficients as we recurse. At the base case, `gcd(a, 0) = a`, so `x = 1, y = 0` (since `a · 1 + 0 · 0 = a`). As we unwind, suppose the recursive call returned `gcd = b · x1 + (a mod b) · y1`. We need to express the same `gcd` as `a · x + b · y`. Substitute `a mod b = a − (a / b) · b` (where `a / b` is integer division):\n\n`gcd = b · x1 + (a − (a / b) · b) · y1 = a · y1 + b · (x1 − (a / b) · y1)`\n\nReading off the coefficients of `a` and `b`:\n\n\n```shell\nx = y1\ny = x1 - (a / b) * y1\n```\n\n\n\n```mermaid\nflowchart LR\n A[\"extgcd(48, 18)\"]:::primary\n B[\"extgcd(18, 12)\"]:::primary\n C[\"extgcd(12, 6)\"]:::primary\n D[\"extgcd(6, 0)
base: x=1, y=0\"]:::green\n\n A --> B\n B --> C\n C --> D\n\n D -->|\"unwind\"| E[\"x=0, y=1
12*0 + 6*1 = 6\"]:::orange\n E -->|\"unwind\"| F[\"x=1, y=-1
18*1 + 12*(-1) = 6\"]:::orange\n F -->|\"unwind\"| G[\"x=-1, y=3
48*(-1) + 18*3 = 6\"]:::teal\n\n classDef primary fill:#00ceff,stroke:#000,color:#000\n classDef orange fill:#ffa94d,stroke:#000,color:#000\n classDef green fill:#69db7c,stroke:#000,color:#000\n classDef teal fill:#38d9a9,stroke:#000,color:#000\n```\n\n\nWe can verify: 48 · (-1) + 18 · 3 = -48 + 54 = 6.\n\n### Modular Inverse via Extended GCD\n\nThe modular inverse of `a` modulo `m` is an integer `x` such that `a · x ≡ 1 (mod m)`. It exists if and only if `gcd(a, m) = 1`. Fermat's little theorem gives a clean formula when `m` is prime (`a^(m-2) mod m`), but when `m` is composite, Extended Euclidean is the standard way.\n\nFrom Bezout's identity, if `gcd(a, m) = 1` then there exist integers `x, y` with `a · x + m · y = 1`. Reducing modulo `m`, the `m · y` term vanishes and we get `a · x ≡ 1 (mod m)`, so `x mod m` is the inverse. The `x` from extended GCD can be negative; normalize with `((x % m) + m) % m`.\n\n\n```java\n// Returns the modular inverse of a mod m, or -1 if it does not exist.\npublic static long modInverse(long a, long m) {\n long[] x = new long[1], y = new long[1];\n long g = extendedGcd(a, m, x, y);\n if (g != 1) return -1; // inverse exists iff gcd(a, m) == 1\n return ((x[0] % m) + m) % m; // normalize to [0, m)\n}\n\n// Extended GCD for long inputs.\nprivate static long extendedGcd(long a, long b, long[] x, long[] y) {\n if (b == 0) { x[0] = 1; y[0] = 0; return a; }\n long[] x1 = new long[1], y1 = new long[1];\n long g = extendedGcd(b, a % b, x1, y1);\n x[0] = y1[0];\n y[0] = x1[0] - (a / b) * y1[0];\n return g;\n}\n```\n\n```python\ndef mod_inverse(a: int, m: int) -> int:\n \"\"\"Returns the modular inverse of a mod m, or -1 if it does not exist.\"\"\"\n g, x, _ = extended_gcd(a, m)\n if g != 1:\n return -1 # inverse exists iff gcd(a, m) == 1\n return (x % m + m) % m # normalize to [0, m)\n\ndef extended_gcd(a: int, b: int) -> tuple[int, int, int]:\n if b == 0:\n return a, 1, 0\n g, x1, y1 = extended_gcd(b, a % b)\n return g, y1, x1 - (a // b) * y1\n```\n\n```cpp\n// Extended GCD for long long inputs.\nlong long extendedGcd(long long a, long long b, long long &x, long long &y) {\n if (b == 0) { x = 1; y = 0; return a; }\n long long x1, y1;\n long long g = extendedGcd(b, a % b, x1, y1);\n x = y1;\n y = x1 - (a / b) * y1;\n return g;\n}\n\n// Returns the modular inverse of a mod m, or -1 if it does not exist.\nlong long modInverse(long long a, long long m) {\n long long x, y;\n long long g = extendedGcd(a, m, x, y);\n if (g != 1) return -1; // inverse exists iff gcd(a, m) == 1\n return ((x % m) + m) % m; // normalize to [0, m)\n}\n```\n\n```go\npackage main\n\n// Extended GCD: returns gcd, and sets x, y such that a*x + b*y = gcd.\nfunc extendedGcdMI(a, b int64, x, y *int64) int64 {\n if b == 0 {\n *x = 1\n *y = 0\n return a\n }\n var x1, y1 int64\n g := extendedGcdMI(b, a%b, &x1, &y1)\n *x = y1\n *y = x1 - (a/b)*y1\n return g\n}\n\n// Returns the modular inverse of a mod m, or -1 if it does not exist.\nfunc modInverse(a, m int64) int64 {\n var x, y int64\n g := extendedGcdMI(a, m, &x, &y)\n if g != 1 {\n return -1 // inverse exists iff gcd(a, m) == 1\n }\n return ((x % m) + m) % m // normalize to [0, m)\n}\n```\n\n```csharp\npublic class ModularInverse\n{\n // Extended GCD for long inputs.\n public static long ExtendedGcd(long a, long b, out long x, out long y)\n {\n if (b == 0)\n {\n x = 1;\n y = 0;\n return a;\n }\n long g = ExtendedGcd(b, a % b, out long x1, out long y1);\n x = y1;\n y = x1 - (a / b) * y1;\n return g;\n }\n\n // Returns the modular inverse of a mod m, or -1 if it does not exist.\n public static long ModInverse(long a, long m)\n {\n long g = ExtendedGcd(a, m, out long x, out long _);\n if (g != 1) return -1; // inverse exists iff gcd(a, m) == 1\n return ((x % m) + m) % m; // normalize to [0, m)\n }\n}\n```\n\n```rust\n// Extended GCD for i64 inputs.\nfn extended_gcd(a: i64, b: i64, x: &mut i64, y: &mut i64) -> i64 {\n if b == 0 {\n *x = 1;\n *y = 0;\n return a;\n }\n let mut x1: i64 = 0;\n let mut y1: i64 = 0;\n let g = extended_gcd(b, a % b, &mut x1, &mut y1);\n *x = y1;\n *y = x1 - (a / b) * y1;\n g\n}\n\n// Returns the modular inverse of a mod m, or -1 if it does not exist.\npub fn mod_inverse(a: i64, m: i64) -> i64 {\n let mut x: i64 = 0;\n let mut y: i64 = 0;\n let g = extended_gcd(a, m, &mut x, &mut y);\n if g != 1 {\n return -1; // inverse exists iff gcd(a, m) == 1\n }\n ((x % m) + m) % m // normalize to [0, m)\n}\n```\n\n```javascript\n// Extended GCD: returns { gcd, x, y } such that a*x + b*y = gcd.\nfunction extendedGcd(a, b) {\n if (b === 0n) return { gcd: a, x: 1n, y: 0n };\n const { gcd, x: x1, y: y1 } = extendedGcd(b, a % b);\n return { gcd, x: y1, y: x1 - (a / b) * y1 };\n}\n\n// Returns the modular inverse of a mod m, or -1n if it does not exist.\nfunction modInverse(a, m) {\n const { gcd, x } = extendedGcd(a, m);\n if (gcd !== 1n) return -1n; // inverse exists iff gcd(a, m) == 1\n return ((x % m) + m) % m; // normalize to [0, m)\n}\n```\n\n```typescript\ninterface ExtGcd { gcd: bigint; x: bigint; y: bigint; }\n\n// Extended GCD: returns { gcd, x, y } such that a*x + b*y = gcd.\nfunction extendedGcd(a: bigint, b: bigint): ExtGcd {\n if (b === 0n) return { gcd: a, x: 1n, y: 0n };\n const { gcd, x: x1, y: y1 } = extendedGcd(b, a % b);\n return { gcd, x: y1, y: x1 - (a / b) * y1 };\n}\n\n// Returns the modular inverse of a mod m, or -1n if it does not exist.\nfunction modInverse(a: bigint, m: bigint): bigint {\n const { gcd, x } = extendedGcd(a, m);\n if (gcd !== 1n) return -1n; // inverse exists iff gcd(a, m) == 1\n return ((x % m) + m) % m; // normalize to [0, m)\n}\n```\n\n\nQuick check: the inverse of 3 mod 11 should satisfy `3x ≡ 1 (mod 11)`. Extended GCD on `(3, 11)` returns `gcd = 1, x = 4, y = -1` because `3 · 4 + 11 · (-1) = 1`. So the inverse is 4, and indeed `3 · 4 = 12 ≡ 1 (mod 11)`.\n\nUse this version whenever the modulus is composite (for example, `mod 2^32` for hash tables, or `mod n` for cyclic structures with `n` not prime). For prime moduli, `power(a, m - 2, m)` from the modular arithmetic chapter is shorter and easier to remember.\n\n### LCM via GCD\n\nThe formula `lcm(a, b) = (a * b) / gcd(a, b)` is straightforward, but there is an important implementation detail. If `a` and `b` are large, their product `a * b` can overflow even a 64-bit integer. The safe way to compute it is:\n\n\n```shell\nlcm(a, b) = (a / gcd(a, b)) * b\n```\n\n\nBy dividing first, you keep the intermediate value small. Since `gcd(a, b)` always divides `a`, the division is exact (no truncation issues).\n\n### GCD of an Array\n\nTo find the GCD of more than two numbers, use the property that GCD is associative:\n\n\n```shell\ngcd(a, b, c) = gcd(gcd(a, b), c)\n```\n\n\nThis means you can fold (reduce) across an array, applying pairwise GCD:\n\n\n```mermaid\nflowchart LR\n A[\"12\"]:::primary --> G1[\"gcd(12, 18)
= 6\"]:::orange\n B[\"18\"]:::primary --> G1\n G1 --> G2[\"gcd(6, 24)
= 6\"]:::orange\n C[\"24\"]:::primary --> G2\n G2 --> G3[\"gcd(6, 15)
= 3\"]:::orange\n D[\"15\"]:::primary --> G3\n G3 --> R[\"Result: 3\"]:::green\n\n classDef primary fill:#00ceff,stroke:#000,color:#000\n classDef orange fill:#ffa94d,stroke:#000,color:#000\n classDef green fill:#69db7c,stroke:#000,color:#000\n```\n\n\nThe same pattern works for LCM of an array: `lcm(a, b, c) = lcm(lcm(a, b), c)`.\n\n---\n\n# Extended GCD Walkthrough\n\nThe regular GCD trace is already shown in the diagram above. The extended version is worth tracing once because the backward pass is where the update rule earns its complexity. Goal: find x, y such that 48x + 18y = 6.\n\n\n```shell\nForward pass (same as regular GCD):\n extgcd(48, 18): q = 48/18 = 2, r = 12 -> extgcd(18, 12)\n extgcd(18, 12): q = 18/12 = 1, r = 6 -> extgcd(12, 6)\n extgcd(12, 6): q = 12/6 = 2, r = 0 -> extgcd(6, 0)\n extgcd(6, 0): base case, return gcd=6, x=1, y=0\n\nBackward pass (update x, y):\n extgcd(12, 6): x = 0, y = 1 - 2*0 = 1 -> 12*0 + 6*1 = 6 ✓\n extgcd(18, 12): x = 1, y = 0 - 1*1 = -1 -> 18*1 + 12*(-1) = 6 ✓\n extgcd(48, 18): x = -1, y = 1 - 2*(-1) = 3 -> 48*(-1) + 18*3 = 6 ✓\n\nResult: x = -1, y = 3\nVerification: 48 * (-1) + 18 * 3 = -48 + 54 = 6 ✓\n```\n\n\n---\n\n# Implementation\n\nBelow are complete implementations. Each includes: iterative GCD, recursive GCD, LCM, extended GCD, and GCD of an array.\n\n\n```java\npublic class GcdLcm {\n\n // Iterative GCD using Euclidean algorithm\n public static int gcd(int a, int b) {\n a = Math.abs(a);\n b = Math.abs(b);\n while (b != 0) {\n int temp = b;\n b = a % b;\n a = temp;\n }\n return a;\n }\n\n // Recursive GCD\n public static int gcdRecursive(int a, int b) {\n a = Math.abs(a);\n b = Math.abs(b);\n if (b == 0) return a;\n return gcdRecursive(b, a % b);\n }\n\n // LCM via GCD (divide first to avoid overflow)\n public static long lcm(long a, long b) {\n if (a == 0 || b == 0) return 0;\n a = Math.abs(a);\n b = Math.abs(b);\n return (a / gcd((int) a, (int) b)) * b;\n }\n\n // Extended GCD: returns gcd, and sets x[0], y[0]\n public static int extendedGcd(int a, int b, int[] x, int[] y) {\n if (b == 0) {\n x[0] = 1;\n y[0] = 0;\n return a;\n }\n int[] x1 = new int[1], y1 = new int[1];\n int g = extendedGcd(b, a % b, x1, y1);\n x[0] = y1[0];\n y[0] = x1[0] - (a / b) * y1[0];\n return g;\n }\n\n // GCD of an array\n public static int gcdArray(int[] nums) {\n int result = nums[0];\n for (int i = 1; i < nums.length; i++) {\n result = gcd(result, nums[i]);\n }\n return result;\n }\n}\n```\n\n```python\ndef gcd(a: int, b: int) -> int:\n \"\"\"Iterative GCD using Euclidean algorithm.\"\"\"\n a, b = abs(a), abs(b)\n while b:\n a, b = b, a % b\n return a\n\ndef gcd_recursive(a: int, b: int) -> int:\n \"\"\"Recursive GCD.\"\"\"\n a, b = abs(a), abs(b)\n if b == 0:\n return a\n return gcd_recursive(b, a % b)\n\ndef lcm(a: int, b: int) -> int:\n \"\"\"LCM via GCD. Python handles big ints natively, but the pattern still applies.\"\"\"\n if a == 0 or b == 0:\n return 0\n a, b = abs(a), abs(b)\n return (a // gcd(a, b)) * b\n\ndef extended_gcd(a: int, b: int) -> tuple[int, int, int]:\n \"\"\"Returns (gcd, x, y) such that a*x + b*y = gcd(a, b).\"\"\"\n if b == 0:\n return a, 1, 0\n g, x1, y1 = extended_gcd(b, a % b)\n return g, y1, x1 - (a // b) * y1\n\ndef gcd_array(nums: list[int]) -> int:\n \"\"\"GCD of an entire array using reduce pattern.\"\"\"\n from functools import reduce\n return reduce(gcd, nums)\n```\n\n```cpp\n#include \n#include \n#include \n\n// Iterative GCD\nint gcd(int a, int b) {\n a = std::abs(a);\n b = std::abs(b);\n while (b != 0) {\n int temp = b;\n b = a % b;\n a = temp;\n }\n return a;\n}\n\n// Recursive GCD\nint gcdRecursive(int a, int b) {\n a = std::abs(a);\n b = std::abs(b);\n if (b == 0) return a;\n return gcdRecursive(b, a % b);\n}\n\n// LCM via GCD (divide first to avoid overflow)\nlong long lcm(long long a, long long b) {\n if (a == 0 || b == 0) return 0;\n a = std::abs(a);\n b = std::abs(b);\n return (a / gcd(static_cast(a), static_cast(b))) * b;\n}\n\n// Extended GCD\nint extendedGcd(int a, int b, int &x, int &y) {\n if (b == 0) {\n x = 1;\n y = 0;\n return a;\n }\n int x1, y1;\n int g = extendedGcd(b, a % b, x1, y1);\n x = y1;\n y = x1 - (a / b) * y1;\n return g;\n}\n\n// GCD of an array\nint gcdArray(const std::vector& nums) {\n int result = nums[0];\n for (size_t i = 1; i < nums.size(); i++) {\n result = gcd(result, nums[i]);\n }\n return result;\n}\n```\n\n```go\npackage main\n\nimport \"math\"\n\n// Iterative GCD using Euclidean algorithm\nfunc gcd(a int, b int) int {\n\ta = int(math.Abs(float64(a)))\n\tb = int(math.Abs(float64(b)))\n\tfor b != 0 {\n\t\ttemp := b\n\t\tb = a % b\n\t\ta = temp\n\t}\n\treturn a\n}\n\n// Recursive GCD\nfunc gcdRecursive(a int, b int) int {\n\ta = int(math.Abs(float64(a)))\n\tb = int(math.Abs(float64(b)))\n\tif b == 0 {\n\t\treturn a\n\t}\n\treturn gcdRecursive(b, a%b)\n}\n\n// LCM via GCD (divide first to avoid overflow)\nfunc lcm(a, b int64) int64 {\n\tif a == 0 || b == 0 {\n\t\treturn 0\n\t}\n\ta = int64(math.Abs(float64(a)))\n\tb = int64(math.Abs(float64(b)))\n\treturn (a / int64(gcd(int(a), int(b)))) * b\n}\n\n// Extended GCD: returns gcd, and sets x, y\nfunc extendedGcd(a, b int, x, y *int) int {\n\tif b == 0 {\n\t\t*x = 1\n\t\t*y = 0\n\t\treturn a\n\t}\n\tvar x1, y1 int\n\tg := extendedGcd(b, a%b, &x1, &y1)\n\t*x = y1\n\t*y = x1 - (a/b)*y1\n\treturn g\n}\n\n// GCD of an array\nfunc gcdArray(nums []int) int {\n\tresult := nums[0]\n\tfor i := 1; i < len(nums); i++ {\n\t\tresult = gcd(result, nums[i])\n\t}\n\treturn result\n}\n```\n\n```csharp\npublic class GcdLcm\n{\n // Iterative GCD\n public static int Gcd(int a, int b)\n {\n a = Math.Abs(a);\n b = Math.Abs(b);\n while (b != 0)\n {\n int temp = b;\n b = a % b;\n a = temp;\n }\n return a;\n }\n\n // Recursive GCD\n public static int GcdRecursive(int a, int b)\n {\n a = Math.Abs(a);\n b = Math.Abs(b);\n if (b == 0) return a;\n return GcdRecursive(b, a % b);\n }\n\n // LCM via GCD\n public static long Lcm(long a, long b)\n {\n if (a == 0 || b == 0) return 0;\n a = Math.Abs(a);\n b = Math.Abs(b);\n return (a / Gcd((int)a, (int)b)) * b;\n }\n\n // Extended GCD\n public static int ExtendedGcd(int a, int b, out int x, out int y)\n {\n if (b == 0)\n {\n x = 1;\n y = 0;\n return a;\n }\n int g = ExtendedGcd(b, a % b, out int x1, out int y1);\n x = y1;\n y = x1 - (a / b) * y1;\n return g;\n }\n\n // GCD of an array\n public static int GcdArray(int[] nums)\n {\n int result = nums[0];\n for (int i = 1; i < nums.Length; i++)\n {\n result = Gcd(result, nums[i]);\n }\n return result;\n }\n}\n```\n\n```rust\npub struct GcdLcm;\n\nimpl GcdLcm {\n // Iterative GCD using Euclidean algorithm\n pub fn gcd(mut a: i32, mut b: i32) -> i32 {\n a = a.abs();\n b = b.abs();\n while b != 0 {\n let temp = b;\n b = a % b;\n a = temp;\n }\n a\n }\n\n // Recursive GCD\n pub fn gcd_recursive(mut a: i32, mut b: i32) -> i32 {\n a = a.abs();\n b = b.abs();\n if b == 0 {\n return a;\n }\n Self::gcd_recursive(b, a % b)\n }\n\n // LCM via GCD (divide first to avoid overflow)\n pub fn lcm(a: i64, b: i64) -> i64 {\n if a == 0 || b == 0 {\n return 0;\n }\n let a = a.abs();\n let b = b.abs();\n (a / Self::gcd(a as i32, b as i32) as i64) * b\n }\n\n // Extended GCD: returns gcd, and sets x, y\n pub fn extended_gcd(a: i32, b: i32, x: &mut i32, y: &mut i32) -> i32 {\n if b == 0 {\n *x = 1;\n *y = 0;\n return a;\n }\n let mut x1 = 0;\n let mut y1 = 0;\n let g = Self::extended_gcd(b, a % b, &mut x1, &mut y1);\n *x = y1;\n *y = x1 - (a / b) * y1;\n g\n }\n\n // GCD of an array\n pub fn gcd_array(nums: &[i32]) -> i32 {\n let mut result = nums[0];\n for i in 1..nums.len() {\n result = Self::gcd(result, nums[i]);\n }\n result\n }\n}\n```\n\n```javascript\n// Iterative GCD\nfunction gcd(a, b) {\n a = Math.abs(a);\n b = Math.abs(b);\n while (b !== 0) {\n [a, b] = [b, a % b];\n }\n return a;\n}\n\n// Recursive GCD\nfunction gcdRecursive(a, b) {\n a = Math.abs(a);\n b = Math.abs(b);\n if (b === 0) return a;\n return gcdRecursive(b, a % b);\n}\n\n// LCM via GCD (divide first to avoid precision issues with large numbers)\nfunction lcm(a, b) {\n if (a === 0 || b === 0) return 0;\n a = Math.abs(a);\n b = Math.abs(b);\n return (a / gcd(a, b)) * b;\n}\n\n// Extended GCD: returns { gcd, x, y }\nfunction extendedGcd(a, b) {\n if (b === 0) {\n return { gcd: a, x: 1, y: 0 };\n }\n const result = extendedGcd(b, a % b);\n return {\n gcd: result.gcd,\n x: result.y,\n y: result.x - Math.floor(a / b) * result.y\n };\n}\n\n// GCD of an array\nfunction gcdArray(nums) {\n return nums.reduce((acc, val) => gcd(acc, val));\n}\n```\n\n```typescript\n// Iterative GCD\nfunction gcd(a: number, b: number): number {\n a = Math.abs(a);\n b = Math.abs(b);\n while (b !== 0) {\n [a, b] = [b, a % b];\n }\n return a;\n}\n\n// Recursive GCD\nfunction gcdRecursive(a: number, b: number): number {\n a = Math.abs(a);\n b = Math.abs(b);\n if (b === 0) return a;\n return gcdRecursive(b, a % b);\n}\n\n// LCM via GCD\nfunction lcm(a: number, b: number): number {\n if (a === 0 || b === 0) return 0;\n a = Math.abs(a);\n b = Math.abs(b);\n return (a / gcd(a, b)) * b;\n}\n\n// Extended GCD\ninterface ExtGcdResult {\n gcd: number;\n x: number;\n y: number;\n}\n\nfunction extendedGcd(a: number, b: number): ExtGcdResult {\n if (b === 0) {\n return { gcd: a, x: 1, y: 0 };\n }\n const result = extendedGcd(b, a % b);\n return {\n gcd: result.gcd,\n x: result.y,\n y: result.x - Math.floor(a / b) * result.y\n };\n}\n\n// GCD of an array\nfunction gcdArray(nums: number[]): number {\n return nums.reduce((acc, val) => gcd(acc, val));\n}\n```\n\n\n---\n\n# Complexity Analysis\n\n### Time Complexity\n\nThe Euclidean algorithm runs in **O(log(min(a, b)))** time.\n\nWhy? At each step, the remainder `a % b` is strictly less than `b`, and it can be shown that after two consecutive steps, the value of `b` is reduced by at least half. This means the number of steps is at most `2 * log2(min(a, b))`, which is O(log(min(a, b))).\n\nMore precisely, the worst case occurs when `a` and `b` are consecutive Fibonacci numbers (for example, gcd(89, 55) takes the maximum number of steps for inputs of that size). This is because Fibonacci numbers produce the smallest possible remainders at each step, making the algorithm work the hardest.\n\n### Space Complexity\n\n- **Iterative version:** O(1), just a few variables.\n- **Recursive version:** O(log(min(a, b))) due to the call stack.\n- **GCD of array:** O(1) extra space (iterative pairwise reduction).\n\n### LCM Complexity\n\nLCM is one GCD call plus constant-time arithmetic, so it is also O(log(min(a, b))).\n\n### GCD of Array\n\nFor an array of `n` elements, computing GCD requires `n - 1` pairwise GCD calls. If the maximum element is `M`, the total time is O(n * log(M)).\n\n\n```mermaid\nflowchart LR\n subgraph Complexity[\"Time Complexity Comparison\"]\n direction TB\n N[\"Naive: O(min(a,b))
Check all divisors\"]:::red\n E[\"Euclidean: O(log(min(a,b)))
Repeated modulo\"]:::green\n end\n\n subgraph Example[\"For a = 1,000,000, b = 999,999\"]\n direction TB\n N2[\"Naive: ~999,999 steps\"]:::red\n E2[\"Euclidean: ~20 steps\"]:::green\n end\n\n N --- N2\n E --- E2\n\n classDef red fill:#ff8787,stroke:#000,color:#000\n classDef green fill:#69db7c,stroke:#000,color:#000\n```\n","pageType":"dsa"}

GCD and LCM

Get Premium