Question

(a) Show that if \({a_1},{a_2},\, \cdots ,\,{a_n}\) are positive integers then\(gcd\left( {{a_1},{a_2},\, \cdots ,\,{a_{n - 1}},\,{a_n}} \right) = gcd\left( {{a_1},{a_2},\, \cdots {a_{n - 2}},\,gcd\left( {{a_{n - 1}},\,{a_n}} \right)} \right)\).

(b) Use part (a), together with the Euclidean algorithm, to develop a recursive algorithm for computing the greatest common divisor of a set of \(n\) positive integers.

Short answer

(a) We proved that \(\gcd \left( {{a_1},\,{a_2},\, \ldots ,\,{a_{n - 1}},\,{a_n}\,} \right) = \gcd \left( {{a_1},\,{a_2},\, \ldots ,\,{a_{n - 2}},\,\gcd \left( {{a_{n - 1}},\,{a_n}} \right)\,} \right)\)

(b)Greatest common divisor is computed by recursive algorithm using Euclidean algorithm.

Step-by-step solution

To recall definition of Greatest common divisor

Greatest Common Divisor (GCD):

An integer\(d\)is said to be the greatest common divisor of two integers\(a\)and\(b\)if –

1)\(d|a,\,d|b\)

2) If \(c|a,\,c|b\), then \(c \le d\), for all integers \(c\).

(a) To prove \(gcd\left( {{a_1},{a_2},\, \cdots ,\,{a_{n - 1}},\,{a_n}} \right) = gcd\left( {{a_1},{a_2},\, \cdots {a_{n - 2}},\,gcd\left( {{a_{n - 1}},\,{a_n}} \right)} \right)\)

Let, \(d = \gcd \left( {{a_1},\,{a_2},\, \ldots ,\,{a_{n - 1}},\,{a_n}\,} \right)\).

This implies that \(d\) is the divisor of \({a_1},\,{a_2},\, \ldots ,\,{a_{n - 1}},\,{a_n}\).

This also implies that \(d\) is the divisor of \(\left( {{a_{n - 1}},\,{a_n}} \right)\) since \(d|{a_{n - 1}}\) and \(d|{a_n}\).

Thus, \(d\) is the divisor of \(\gcd \left( {{a_1},\,{a_2},\, \ldots ,\,{a_{n - 2}},\,\gcd \left( {{a_{n - 1}},\,{a_n}} \right)\,} \right)\) since \(d\) divides \({a_1},\,{a_2},\, \ldots ,\,{a_{n - 2}},\,\gcd \left( {{a_{n - 1}},\,{a_n}} \right)\).

Then \(\gcd \left( {{a_1},\,{a_2},\, \ldots ,\,{a_{n - 1}},\,{a_n}\,} \right) \le \gcd \left( {{a_1},\,{a_2},\, \ldots ,\,{a_{n - 2}},\,\gcd \left( {{a_{n - 1}},\,{a_n}} \right)\,} \right)\,\)…….. (1)

Let, \(b = \gcd \left( {{a_1},\,{a_2},\, \ldots ,\,{a_{n - 2}},\,\gcd \left( {{a_{n - 1}},\,{a_n}} \right)\,} \right)\).

This implies that \(b\) is the divisor of \({a_1},\,{a_2},\, \ldots ,\,{a_{n - 2}},\,\gcd \left( {{a_{n - 1}},\,{a_n}} \right)\).

Since we have

\(\begin{aligned}{l}b|\gcd \left( {{a_{n - 1}},\,{a_n}} \right)\\ \Rightarrow b|{a_{n - 1}},\,b|{a_n}\end{aligned}\)

This also implies that

\(b|\gcd \left( {{a_1},\,{a_2},\, \ldots ,\,{a_{n - 2}},\,\gcd \left( {{a_{n - 1}},\,{a_n}} \right)\,} \right)\)since \(b|{a_1},\,{a_2},\, \ldots ,\,{a_n}\).

Therefore, \(\gcd \left( {{a_1},\,{a_2},\, \ldots ,\,{a_{n - 1}},\,{a_n}\,} \right) \ge \gcd \left( {{a_1},\,{a_2},\, \ldots ,\,{a_{n - 2}},\,\gcd \left( {{a_{n - 1}},\,{a_n}} \right)\,} \right)\)…….. (2)

From (1) and (2), we get,

\(\gcd \left( {{a_1},\,{a_2},\, \ldots ,\,{a_{n - 1}},\,{a_n}\,} \right) = \gcd \left( {{a_1},\,{a_2},\, \ldots ,\,{a_{n - 2}},\,\gcd \left( {{a_{n - 1}},\,{a_n}} \right)\,} \right)\).

(b) To develop a recursive algorithm

We call the algorithm the “gcd” and the input is the list of \(n\) positive integers with \(n \ge 2\).

Procedure: \(\gcd \left( {{a_1},\,{a_2},\, \ldots ,\,{a_n}:n \ge 2} \right)\).

If \(n = 2\), then input contains only two integers.

Using Euclidean algorithm we will determine the greatest common divisor of two integers.

if n=2 then

return Euclidean \(\left( {{a_1},\,{a_2}} \right)\)

If \(n > 2\), then we use the result of part (a) to determine the greatest common divisor.

else

\({a_{n - 1}}\): Euclidean \(\left( {{a_{n - 1}},\,{a_n}} \right)\)

return \(\gcd \left( {{a_1},\,{a_2},\, \ldots ,\,{a_{n - 1}}} \right)\)