Greatest common divisor
The greatest common divisor (gcd) or highest common factor (HCF) of two integers x and y, usually written as [math]\displaystyle{ \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.
Algorithm
The GCD of any two positive integers can be defined as a recursive function: [math]\displaystyle{ \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.
Greatest Common Divisor Media
A 24-by-60 rectangle is covered with ten 12-by-12 square tiles, where 12 is the GCD of 24 and 60. More generally, an a-by-b rectangle can be covered with square tiles of side length c only if c is a common divisor of a and b.
Animation showing an application of the Euclidean algorithm to find the greatest common divisor of 62 and 36, which is 2.
Related pages
References
- ↑ "Comprehensive List of Algebra Symbols". Math Vault. 2020-03-25. Retrieved 2020-08-30.
- ↑ Weisstein, Eric W. "Greatest Common Divisor". mathworld.wolfram.com. Retrieved 2020-08-30.
- ↑ "Greatest Common Factor". www.mathsisfun.com. Retrieved 2020-08-30.