Algorithm 6: The division algorithm

Input: Integers a 0 and b > 0 Output: Integers q and r for which a = qb + r and 0 r < b

begin

q := 0

while a b do a := a b

q := q +1

end

r := a

output r

end

Q: Rewrite the division algorithm as a recursive procedure Div. It should take as input two numbers a,b and return an ordered pair (q, r), where a = qb + r with 0 r b. Example: Div(25,3) = (8,1).