GCD (Greatest Common Divisor) GCD of two positive integers is the largest number that divides both of them.
Method 1: Using Prime Factorization
Find GCD of 60 and 84
Step 1: Prime factorize both numbers
60 = 22 × 3 × 5
84 = 22 × 3 × 7
Step 2: Take the common prime factors with the smallest powers:
22 × 3 × 5
22 × 3 × 7
Common primes: 22 and 31
GCD = 22 × 3
GCD = 4 × 3
GCD = 12
Find GCD of 36 and 48
Step 1: Prime factorize both numbers
36 = 22 × 3² × 3
36 = 22 × 3 × 3
48 = 2⁴ × 3
48 = 22 × 22 × 3
Step 2: Take the common prime factors with the smallest powers:
22 × 3 × 3
22 × 22 × 3
Common primes: 2² and 3¹
GCD = 2² × 3
GCD = 4 × 3
GCD = 12
Find GCD of 45 and 75
Step 1: Prime factorize both numbers
45 = 3 × 3 × 5 = 3² × 5
75 = 3 × 5 × 5 = 3 × 5²
Step 2: Take the common prime factors with the smallest powers:
3 × 3 × 5
3 × 5 × 5
Common primes: 3¹ and 5¹
GCD = 3 × 5
GCD = 15
Euclidean Algorithm
The Euclidean Algorithm is a method used to find the Greatest Common Divisor (GCD) of two integers. The GCD is the largest positive integer that divides both numbers without leaving a remainder.
The algorithm works by repeatedly dividing the larger number by the smaller number and using the remainder until the remainder becomes 0. The last non-zero remainder is the GCD.
Method 2: Using the Euclidean Algorithm
The Euclidean Algorithm finds the GCD faster using repeated division.
Find GCD of 60 and 84
Step 1: 84 ÷ 60 = 1 remainder 24
Step 2: 60 ÷ 24 = 2 remainder 12
Step 3: 24 ÷ 12 = 2 remainder 0
When remainder becomes 0, the last non-zero remainder is the GCD.
GCD (60,84) = 12
Find GCD of 36 and 48
Step 1: 48 ÷ 36 = 1 remainder 12
Step 2: 36 ÷ 12 = 3 remainder 0
GCD (36,48) = 12
Find GCD of 45 and 75
Step 1: 75 ÷ 45 = 1 remainder 30
Step 2: 45 ÷ 30 = 1 remainder 15
Step 3: 30 ÷ 15 = 2 remainder 0
GCD (45,75) = 15
Find GCD of 56 and 98
Step 1: 98 ÷ 56 = 1 remainder 42
Step 2: 56 ÷ 42 = 1 remainder 14
Step 3: 42 ÷ 14 = 3 remainder 0
GCD (56,98) = 14