Integer Division

Euclid's algorithm is a sequence of integer divisions. Given two numbers a and b, where b is smaller than a, we may divide

$$a= q\cdot b + r$$

where q is an integer called the quotient and r is an integer called the remainder which must satisfy $0 \le r < b$.

Suppose a=97 and b=13. Then $97=7\cdot 13+ 6$, which means q=7and r=6.