GCD Formulas
Master the Greatest Common Divisor with comprehensive formulas and algorithms. From basic methods to advanced techniques for finding GCD efficiently.
1GCD Definition
The Greatest Common Divisor (GCD) of two or more integers is the largest positive integer that divides each number without remainder.
Properties:
- •
- •
- •
Example:
Because 6 is the largest number that divides both 48 and 18.
2Euclidean Algorithm
The most efficient method for computing GCD, based on the principle that GCD doesn't change if we replace the larger number with the remainder of division.
Algorithm Steps:
Example: GCD(48, 18)
3Prime Factorization Method
Find GCD by expressing each number as a product of prime factors and taking the minimum power of each common prime.
Example: GCD(60, 48)
4Extended Euclidean Algorithm
Not only finds GCD but also finds integers x and y such that ax + by = gcd(a,b).
Bézout's Identity
For any integers a and b, there exist integers x and y such that: