$m=n(q)+{r}_{1}\phantom{\rule{0ex}{0ex}}n=({r}_{1})({q}_{2})+{r}_{2}\phantom{\rule{0ex}{0ex}}{r}_{1}=({r}_{2})({q}_{3})+{r}_{3}\phantom{\rule{0ex}{0ex}}{r}_{2}=({r}_{3})({q}_{4})+{r}_{4}$

and so on, until

${r}_{n\mathrm{\_}1}=({r}_{n})({q}_{n+1})+{r}_{n+1}\phantom{\rule{0ex}{0ex}}{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.