Greatest Common Divisor

number-theory

Definition

Greatest Common Divisor

The greatest common divisor of $a$ and $b$ is the largest integer $d$ such that $d$ divides both $a$ and $b$.

$$\gcd (a,b)=\max \left\{d\in \mathbb{Z}\mid d|a\wedge d|b\right\}$$

Fundamental Theorem of Arithmetic

Using the fundamental theorem of arithmetic, the greatest common divisor of $n,k\in \mathbb{Z}$ can be represented as:

$$\gcd (n,k)=\prod _i{p}_i^{\min (e_i(n),e_i(k))}$$

This can be useful when proving distribution laws for distributive lattices.