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.

ingwadlatp 2022-08-01 Answered
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.
You can still ask an expert for help

Expert Community at Your Service

  • Live experts 24/7
  • Questions are typically answered in as fast as 30 minutes
  • Personalized clear answers
Learn more

Solve your problem for the price of one coffee

  • Available 24/7
  • Math expert for every subject
  • Pay only if we can solve it
Ask Question

Answers (1)

Ali Harper
Answered 2022-08-02 Author has 16 answers
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.
Not exactly what you’re looking for?
Ask My Question

Expert Community at Your Service

  • Live experts 24/7
  • Questions are typically answered in as fast as 30 minutes
  • Personalized clear answers
Learn more

New questions