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
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