> [!NOTE] Definition (GCD of two natural numbers) > Suppose that $a$ and $b$ are [[Natural Numbers|natural numbers]]. We define $\gcd(a,b) = \begin{cases} 0 & \text{if $a=b=0$} \\ \max (D(a) \cap D(b)) &\text{ otherwise} \end{cases}$where $D(n)=\{ d\in \mathbb{N} : d \mid n \}$ is the set of numbers that [[Divisibility in Integers|divide]] $n.$ # Properties By [[GCD and LCM from prime factorisation]], if $a = \prod p_{i}^{\alpha_{i}}$ and $b = \prod p_{i}^{\beta_{i}}$ then $\gcd(a,b)=\prod p_{i}^{\min(\alpha_{i},\beta_{i})}.$ By [[GCD of integers with common divisor]], $\gcd(km,kn)=|k|\gcd(m,n).$ By [[Integers divided by GCD are coprime]], a common divisor $d$ of integers $a,b$ that are not both zero is the greatest common divisor of $a$ and $b$ iff $\gcd\left( \frac{a}{d}, \frac{b}{d} \right)=1.$ **Note** [[Product of LCM and GCD]]. **Computation**: [[Euclid's Algorithm]] can be used to compute the gcd of two non-equal positive natural numbers. **Bézout's Lemma**: [[Bézout's lemma|Bézout's lemma]] asserts that the gcd of two numbers can be written as a linear combination of both of them.