📐

GCD and LCM

★☆☆☆☆Elementary

📖Definition

GCD (Greatest Common Divisor) is the largest number that divides both numbers. LCM (Least Common Multiple) is the smallest number divisible by both.

gcd(a, b) × lcm(a, b) = a × b

Relationship between GCD and LCM

gcd(a, b) = gcd(b, a mod b)

Euclidean algorithm

예제 1★☆☆☆☆

Find GCD(24, 36) and LCM(24, 36).

예제 2★★☆☆☆

Find GCD(48, 18) using Euclidean algorithm.

Simplifying, finding common denominators

Synchronizing periodic events

RSA key generation

#number#fundamental#gcd#lcm#elementary