Question

what do you mean by euclids division algorithum?

Answer 1

The division algorithm, sometimes called the Euclidean division algorithm, says that for positive integers aa (the dividend) and bb (the divisor), there exist unique nonnegative integers r<br<b and qq, called the remainderand quotient, such that a=bq+ra=bq+r.

The algorithm is to repeatedly subtract bbfrom aa until you reach a remainder less than bb. Then qq is the number of subtractions you performed.

Although that algorithm works, the one humans learn in grade school is long division.

Answer 2

Theorem = If a and b are positive integers such that a= bq+r, than every comman divisor of a and b is a comman divisor of b and r, and vice-versa