The Greatest Common Divisor (GCD) of two or more integers is the largest positive integer that divides each number without remainder.
Euclidean Algorithm:
- • Based on the principle: GCD(a,b) = GCD(b, a mod b)
- • Continues until remainder is 0
- • Very efficient for large numbers
- • Named after ancient Greek mathematician Euclid
Properties:
- • GCD(a, b) = GCD(b, a) (commutative)
- • GCD(a, 0) = |a|
- • GCD(a, 1) = 1 for any integer a
- • If GCD(a, b) = 1, then a and b are coprime
Applications:
- • Simplifying fractions to lowest terms
- • Cryptography and number theory
- • Computer graphics and pixel manipulation
- • Music theory (rhythm and beat patterns)
- • Solving Diophantine equations