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.

Ali Harper · Accepted Answer

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.

Answered question

Answer & Explanation

New Questions in High school geometry