GCD Algorithm
Module 02 / Lesson 03
Video Explanation
Understanding GCD
GCD, also known as Greatest Common Factor (GCF), is the largest positive integer that divides two or more numbers without leaving a remainder. It represents the largest shared factor between numbers.
Key Properties:
- GCD(a, b) = GCD(b, a)
- GCD(a, 0) = |a|
- GCD(a, 1) = 1
- GCD(a, b) is always positive
Common Methods:
- Listing Factors Method
- Euclidean Algorithm
- Prime Factorization
Numerical Example: GCD(48, 36)
Factors of 48: 1, 2, 3, 4, 6, 8, 12, 16, 24, 48
Factors of 36: 1, 2, 3, 4, 6, 9, 12, 18, 36
Shared Factors: 1, 2, 3, 4, 6, 12.
Result: GCD = 12
Python GCD Logic
import math
# Method 1: Using built-in function
num1, num2 = 48, 36
print(f"GCD using math module: {math.gcd(num1, num2)}")
# Method 2: Manual Implementation (Euclidean)
def calculate_gcd(a, b):
while b:
a, b = b, a % b
return a
print(f"GCD using manual function: {calculate_gcd(48, 36)}")