How to Calculate Gcf
What is Gcf?
The Greatest Common Factor (GCF), also called Greatest Common Divisor (GCD), is the largest positive integer that divides both numbers without a remainder. It is used to simplify fractions and solve equations.
Step-by-Step Guide
- 1Euclidean Algorithm: repeatedly divide, then swap: GCF(a,b) = GCF(b, a mod b)
- 2Continue until remainder = 0
- 3The last non-zero remainder is the GCF
Worked Examples
Input
GCF(48, 18)
Result
6
48=6×8, 18=6×3
Input
GCF(100, 75)
Result
25
GCF(100,75)=GCF(75,25)=GCF(25,0)=25