Question

state Euclid's division algorithm

Answer 1

If a and b are positive integers such that a = bq + r, then every common divisor of a and b is a common divisor of b and r, and vice-versa.