The question is as follows:
(1): Let m and n be positive integers with n < m and let r be the remainder when m is divided by n. Prove that
$$r < \frac m2$$
(2): The Euclidean Algorithm for the positive integers $r_0 > r_1$works by repeated division with remainders.
$$r_0 = q_1r_1 + r_2, 0\le r_2\le r_1,$$
$$r_1 = q_2r_2 + r_3, 0\le r_3\le r_2,$$
and so on...
$r_n$ is the greatest common divisor of $r_0$ and $r_1$ when the following $r$ is 0.
Show that if $r_0\le2^k$ with $k\ge1$, then $n\le 2k-1$.
I have answered part 1, but I left it here as I assume it is required for part 2. Thanks.