For positive integers
a and
b, there exist unique integers
q and
r such that
a = bq + r, where
0 ≤ r < b. Here
q is the quotient and
r is the remainder.
Repeated application of this result gives
Euclid’s division algorithm, which is a systematic method for finding the HCF of two positive integers.
HCF by Euclid’s Algorithm
To find HCF(867, 255):
867 = 255 × 3 + 102
255 = 102 × 2 + 51
102 = 51 × 2 + 0
Therefore HCF = 51.