Find the greatest common factor of two numbers — with Euclid’s algorithm shown step by step, and the LCM as a bonus.
How the GCF is found
The greatest common factor (also called GCD or HCF) is the largest number dividing both inputs cleanly. Rather than listing every factor — slow and error-prone for big numbers — this calculator runs Euclid’s algorithm, the 2,300-year-old method that repeatedly replaces the larger number with the remainder of the division, and shows each step so the working can go straight onto homework.
How to use it
- Enter the two whole numbers.
- Read the GCF.
- Follow Euclid’s steps underneath — the last non-zero remainder is the answer.
The algorithm
A worked example
For 48 and 36: 48 = 1×36 + 12, then 36 = 3×12 + 0 — remainder zero, so the GCF is 12. Two steps instead of listing eighteen factors. The bonus row shows the LCM, 144, via the identity a×b ÷ GCF. The everyday use is simplifying fractions: 36/48 divided top and bottom by 12 is 3/4 in one move.