kidzsearch.com > wiki Explore:web images videos games

# Greatest common divisor

The **greatest common divisor** (**gcd**) or **highest common factor **(**HCF**) of two integers *x* and *y*, usually written as [math]\gcd(x, y)[/math], 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.

## Contents

## Algorithm

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

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.

## Related pages

## References

- ↑ "Comprehensive List of Algebra Symbols" (in en-US). 2020-03-25. https://mathvault.ca/hub/higher-math/math-symbols/algebra-symbols/.
- ↑ Weisstein, Eric W.. "Greatest Common Divisor" (in en). https://mathworld.wolfram.com/GreatestCommonDivisor.html.
- ↑ "Greatest Common Factor". https://www.mathsisfun.com/greatest-common-factor.html.