# Greatest common divisor

The greatest common divisor of two numbers, ${\displaystyle x}$ and ${\displaystyle y}$ is the biggest integer that divides both ${\displaystyle x}$ and ${\displaystyle y}$.
This comes in handy when calculating the least common multiple, since ${\displaystyle lcm(a,b)={\frac {ab}{\gcd(a,b)}}}$.
• Any number that divides both ${\displaystyle a}$ and ${\displaystyle b}$ divides ${\displaystyle \gcd(a,b)}$.
• ${\displaystyle \gcd(a,b)}$ is expressible as ${\displaystyle ax+by}$ for some integers ${\displaystyle x}$ and ${\displaystyle y}$(Extended Euclidean algorithm).
• More generally, the equation ${\displaystyle ax+by=c}$ has integer solutions for ${\displaystyle x}$ and ${\displaystyle y}$ if and only if ${\displaystyle \gcd(a,b)\mid c}$. If it has one solution ${\displaystyle (x_{0},y_{0})}$, it has infinitely many solutions, all given by ${\displaystyle (x_{0}+{\frac {b}{gcd(a,b)}}t,y_{0}-{\frac {a}{gcd(a,b)}}t)}$ as ${\displaystyle t}$ takes on all integer values.