*2. in the correctness of the euclid's algorithm, we need to prove
that rm is indeed a greatest common divisor of a and b. this
can be done by proving
(a) r'm divides a and b, and
(b) any integer which divides both a and b also divides rm.
proof that the above two statements are correct.