The Euclidean algorithm starts with two numbers m and n then

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 desired gcd. Prove that r_n+1 is at least a divisor of both m and n.

Solution

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.