All simulatorsClick to start animation
Number SystemReal Numbers
Euclid's Division Algorithm
Run a = bq + r step by step to reach the HCF.
Controls
455
42
Live result
Steps
455 = 42 × 10 + 35 | 42 = 35 × 1 + 7 | 35 = 7 × 5 + 0
HCF
7
Euclid's algorithm — repeated divisionSteps: 455 = 42 × 10 + 35 | 42 = 35 × 1 + 7 | 35 = 7 × 5 + 0
The remainder must satisfy 0 ≤ r < b; when the remainder becomes 0, the divisor is the HCF.