Question

Use Euclid's division algorithms to find the HCF of 657 and 953​

Answer 1

let a=657 b=953

we know a=b×q+r

953÷657=296

953=657×1+296

296÷657=65

657=296×2+65

296÷65=36

296=65×4+36

65÷36=29

65=36×1+29

36÷29=7

36=29×1+7

29÷7=1

29=7×4+1

7÷4=3

7=4×1+3

3÷4=1

4=3×1+1

3÷1=3

3=3×1+0

so hcf=3

so answer is 3