# 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.

The Euclidean algorithm starts with two numbers m and n, then computes
$m=n\left(q\right)+{r}_{1}\phantom{\rule{0ex}{0ex}}n=\left({r}_{1}\right)\left({q}_{2}\right)+{r}_{2}\phantom{\rule{0ex}{0ex}}{r}_{1}=\left({r}_{2}\right)\left({q}_{3}\right)+{r}_{3}\phantom{\rule{0ex}{0ex}}{r}_{2}=\left({r}_{3}\right)\left({q}_{4}\right)+{r}_{4}$
and so on, until
${r}_{n\mathrm{_}1}=\left({r}_{n}\right)\left({q}_{n+1}\right)+{r}_{n+1}\phantom{\rule{0ex}{0ex}}{r}_{n}=\left({r}_{n+1}\right)\left({q}_{n+2}\right)$
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

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

Solve your problem for the price of one coffee

• Math expert for every subject
• Pay only if we can solve it

Ali Harper
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.