euclid'shighestcommonfactoralgorithm

Euclid's Highest Common Factor Algorithm

hcf (a,b)=hcf (a, a-b)

Proof:

Let f=hcf (a,b), let g=hcf(a, a-b)

f|a and f|b, so f|(a-b), and g|a and g|(a-b), so g|b

=> f<=g and g<=f