Originally Posted by

**Matter_Math** So I am back to this problem. I skipped it until it was the last one left.

So here is what I have so far.

Base Case :

If input r, is of the form 1/d, for some number d, then the algorithm haults.

Inductive step :

Assume the input r, is of the form x/y where not x|y and x != 1. Then 0 < x/y < 1.

Now assume 1/d is the largest unit fraction less than x/y. Thus

x/y - 1/d < x/y < 1

x - y/d < x < y

Am I taking the correct step? I am kind of stuck. I am reading your hints and I get it, but I cannot put it into proper notation. Thanks