The Euclidean algorithm starts with two numbers m and n, then computes m = n(q) + r_1 n = (r_1)(q_2) + r_2 r_1 = (r_2)(q_3) + r_3 r_2 = (r_3)(q_4) + r_4 and so on, until r_n_1 = (r_n)(q_n + 1) + r_n + 1 r_n = (r_n + 1)(q_n + 2) and r_n+1 is the desiblack gcd. Prove that r_n+1 is at least a divisor of both m and n.

Question

The Euclidean algorithm starts with two numbers m and n, then computes

m = n (q) + r_{1} n = (r_{1}) (q_{2}) + r_{2} r_{1} = (r_{2}) (q_{3}) + r_{3} r_{2} = (r_{3}) (q_{4}) + r_{4}

and so on, until

r_{n_1} = (r_{n}) (q_{n + 1}) + r_{n + 1} r_{n} = (r_{n + 1}) (q_{n + 2})

and

r_{n + 1}

is the desiblack gcd. Prove that r_n+1 is at least a divisor of both m and n.

Answer 1

In the euclidian algorithm, what we try to do is to break the higher of the two numbers in form of remainder and a prime multiple iterated upto the time till there is no remainder I.e,the bigger number can be expressed in form of a multiple of a smaller number. This smaller number is called GCD.
Such being the case, if you trace it backwards then you will realise that THE GCD will always be present in forum of a multiple as we move up. We move up to the original numbers.
Thus the GCD will always be a divisor of the original two numbers.

Answers (1)

Not exactly what you’re looking for?

You might be interested in

New questions