# Greatest common divisor

largest divisor of two integers or polynomials

The greatest common divisor (gcd) or highest common factor (HCF) of two integers x and y, usually written as ${\displaystyle \gcd(x,y)}$, is the greatest (largest) number that divides both of the integers evenly.[1][2] GCDs are useful in simplifying fractions to the lowest terms.[3] Euclid came up with the idea of GCDs.

## Algorithm

The GCD of any two positive integers can be defined as a recursive function: ${\displaystyle \gcd(u,v)={\begin{cases}\gcd(v,u{\mbox{ mod }}v),&{\mbox{if }}v>0\\u,&{\mbox{if }}v=0\end{cases}}}$

In fact, this is the basis of Euclidean algorithm, which uses repeated long division in order to find the greatest common factor of two numbers.

## Examples

The GCD of 20 and 12 is 4, since 4 times 5 equals 20 and 4 times 3 equals 12. And since 3 and 5 have no common factor, their GCD is 1.

As another example, the GCD of 81 and 21 is 3.

## References

1. "Comprehensive List of Algebra Symbols". Math Vault. 2020-03-25. Retrieved 2020-08-30.
2. Weisstein, Eric W. "Greatest Common Divisor". mathworld.wolfram.com. Retrieved 2020-08-30.
3. "Greatest Common Factor". www.mathsisfun.com. Retrieved 2020-08-30.