Find the Greatest Common Factor (GCF) or Greatest Common Divisor (GCD) of two or more numbers using Euclidean algorithm and prime factorization methods with step-by-step explanations.
Enter positive integers separated by commas (2-10 numbers recommended)
Simple GCF example
GCF of three numbers
Larger numbers with common factors
Numbers with multiple common factors
Numbers with 2 as common factor
Prime numbers (GCF = 1)
Problem 1: Simplify 48/72
What is the GCF of 48 and 72? What is the simplified fraction?
Problem 2: Resource Division
36 students need to be divided into groups of equal size. The maximum group size is the GCF of 36 and what number?
Problem 3: Pattern Recognition
Find the largest number that divides both 84 and 96 evenly.
Problem 4: Three Numbers
What is the GCF of 24, 36, and 48? Try both methods.
Problem 5: Large Numbers
Calculate GCF of 126, 162, and 198. What prime factors do they share?
Fundamental concept in number theory, used in cryptography and modular arithmetic
Simplifying rational expressions and finding common denominators
Used in algorithms for data compression and hash table implementation
Signal processing, gear ratios, and synchronization problems
The Greatest Common Factor (GCF), also known as the Greatest Common Divisor (GCD), is the largest positive integer that divides two or more numbers without leaving a remainder. It represents the largest number that can evenly divide all given numbers.
For integers a, b, and d (where d ≠ 0), d is a common divisor if d divides a and d divides b. The greatest common divisor is the largest such positive integer.
Where ℕ represents the set of natural numbers
The GCF can also be defined as the largest positive integer d such that a = d×m and b = d×n for some integers m and n.
Euclidean Algorithm
An efficient method using repeated division and remainders based on the property that GCF(a, b) = GCF(b, a mod b)
Prime Factorization
Factor each number into primes, then take the product of the lowest power of common primes
List Method
List all divisors of each number and find the greatest common one (works for small numbers)
Bezout's Identity: For any integers a and b, there exist integers x and y such that:
This shows that the GCF can always be expressed as a linear combination of the original numbers.
The Euclidean algorithm has logarithmic time complexity O(log min(a,b)). Each step reduces the problem size by at least half.
Every positive integer greater than 1 can be uniquely expressed as a product of prime numbers. For GCF calculation: