GCD and LCM

The GCD (greatest common divisor) of two numbers is the largest natural number by which both given numbers are divisible without a remainder.

Notation: GCD(a, b). For example, GCD(12, 18) = 6.

The LCM (least common multiple) of two numbers is the smallest natural number that is divisible by both given numbers without a remainder.

Notation: LCM(a, b). For example, LCM(12, 18) = 36.

Method 1 — prime factorization:

• decompose both numbers into prime factors;
• select the common factors;
• multiply them — this will be the GCD.

Example: GCD(24, 36). 24 = 2³ · 3, 36 = 2² · 3². Common factors: 2² · 3 = 12. So GCD(24, 36) = 12.

Method 2 — Euclidean algorithm: divide the larger number by the smaller, then the smaller by the remainder, and so on until zero. The last non-zero remainder is the GCD.

Method 1 — prime factorization:

• decompose both numbers into prime factors;
• select all factors that appear in at least one decomposition, with the maximum exponent;
• multiply them — this will be the LCM.

Example: LCM(24, 36). 24 = 2³ · 3, 36 = 2² · 3². Maximum exponents: 2³ · 3² = 72. So LCM(24, 36) = 72.

Method 2 — via GCD: LCM(a, b) = (a · b) / GCD(a, b).

GCD and LCM are actively used when working with fractions:

• GCD — for reducing fractions (numerator and denominator are divided by GCD);
• LCM — for finding a common denominator (the common denominator is the LCM of the denominators);
• LCM is also used in solving problems on motion, work, and joint actions.

Examples of computing GCD and LCM:

• GCD(12, 18) = 6, LCM(12, 18) = 36;
• GCD(8, 12) = 4, LCM(8, 12) = 24;
• GCD(7, 11) = 1, LCM(7, 11) = 77 (coprime numbers).