Question

Describe a recursive algorithm for writing the greatest common divisor of \(n\) positive integers as a linear combination of these integers.

Short answer

Thus, \({r_n}\) is the greatest common divisor of \(a\;{\rm{and}}\;b\).

Step-by-step solution

Define Greater common divisor.

Consider \(a\;{\rm{and}}\;b\) are integers. Assume \(a,b\) are positive, since Greatest Common Divisor of \(a,b\) is \(GCD\left( {a,b} \right) = GCD\left( { \pm a, \pm b} \right)\). The Euclidean algorithm uses the division algorithm to produce a sequence of quotients and remainders as follows:

\(\begin{aligned}{l}a = b{q_1} + {r_1}\\b &= {r_1}{q_2} + {r_2}\\{r_1} &= {r_2}{q_3} + {r_3}\\....\\{r_{n - 2}} &= {r_{n - 1}}{q_n} + {r_n}\\{r_{n - 1}} &= {r_n}{q_{n + 1}} + 0\end{aligned}\)

Where \({r_n}\) is the last nonzero remainder. The second principle of mathematical induction to prove that \({r_k}\) is a linear combination of \(a\;{\rm{and}}\;b\) for \(1 \le k \le n\).

Apply mathematical induction.

1 Basis step \(\left( {k = 1} \right)\).

\(\begin{aligned}{c}{r_1} &= a - b{q_1}\\ &= a\left( 1 \right) + b\left( { - {q_1}} \right)\end{aligned}\)

2 Induction step. Suppose \({r_1}\) is a linear combination of \(a\;{\rm{and}}\;b\) for \(1 \le i \le k\). For \(1 \le k \le n\) it gives,

\({r_{k + 1}} = {r_{k - 1}} - {r_k}{q_{k + 1}}\)

By the inductive hypothesis \({r_{k + 1}}\) and \({r_k}\) are linear combination of \(a\;{\rm{and}}\;b\).

Thus, write as follows:

\({r_k} = a{s_1} + b{t_1}\)and \({r_k} = a{s_2} + b{t_2}\)

For integers \({s_1}\),\({t_1}\),\({s_2}\),\({t_2}\) and substitute into equation above:

\(\begin{aligned}{c}{r_{k + 1}} &= \left( {a{s_1} + b{t_1}} \right) - \left( {a{s_2} + b{t_2}} \right){q_{k + 1}}\\ &= a\left( {{s_1} - {s_2}{q_{k + 1}}} \right) + b\left( {{t_1} - {t_2}{q_{k + 1}}} \right)\end{aligned}\)

Thus, \({r_{k + 1}}\) is a linear combination of \(a\;{\rm{and}}\;b\). By second principle of mathematical induction, \({r_n}\) is a linear combination of \(a\;{\rm{and}}\;b\). But \({r_n}\) is the greatest common divisor of \(a\;{\rm{and}}\;b\).

Therefore, \({r_n}\) is the greatest common divisor of \(a\;{\rm{and}}\;b\).