Greatest common divisor

From Simple English Wikipedia, the free encyclopedia

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

The GCD of any two positive integers can be defined as a recursive function:

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[change | change source]

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[change | change source]

References[change | change source]

  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.