In Exercise of Section 1.5, a modified division algorithm is given, which states that if a...

In Exercise of Section 1.5, a modified division algorithm is given, which states that if a and b > 0 are integers, then there exist unique integers q, r, and e such that a = bq + er, where e = ±1, r ≥ 0, and −b/2 < er ≤ b/2. We can set up an algorithm, analogous to the Euclidean algorithm, based on this modified division algorithm, called the least-remainder algorithm. It works as follows: Let r0 = a and r1 = b, where a > b > 0. Using the modified division algorithm repeatedly, obtain the greatest common divisor of a and b as the last nonzero remainder rn in the sequence of divisions

Show that the least-remainder algorithm always produces the greatest common divisor of two integers.

Exercise

Show that if a and b are positive integers, then there are unique integers q and r such that a = bq + r. where − b/2 < r ≤ b/2. This result is called the modified division algorithm.