> For the complete documentation index, see [llms.txt](https://mandober.gitbook.io/math-debrief/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://mandober.gitbook.io/math-debrief/501-number-theory/terms/gcd-lcm.md).

# gcd-lcm

## GCD and LCM

If `c` divides both `a` and `b`, then it is their *common divisor*. The largest such number is their **greatest common divisor**, `gcd(a, b)`.

Get GCD of 2 ints by mult their common prime factors. For example: 140=2*2*5*7 and 650=2*5*5*13, so `gcd(140, 6500) = 2*5 = 2`

Common multiple of `a` and `b` is `c` such that `a|c` and `b|c`. The **least common multiple** is the smallest positive number for which this is true.

Computable with: `lcm(a,b) = a*b / gcd(a,b)`

If two ints `a` and `b` share no common factor, then `gcd(a,b)=1`. Such pair is called **relatively prime**.

* if int `k > 0`, then `k | 0`
* `gcd(k,0) = gcd(0,k) = k` 
* `gcd(0,0)` is **not defined** since all ints are common divisors of 0 and 0, so there is no greatest one.

## Greatest Common Divisor

Greatest common divisor (GCD)

* domain: Integers $$\mathbb{Z}$$

  A simple calculator to determine the greatest common divisor of any two regular integers.

gcd(a,b)=\deltagcd(a,b)=δ $$\mathbb{N}$$