Question

For two positive integers a and b, define the function h (a,b) as the greatest common factor (GCF) of a, b. Let A be a set of n positive integers. G(A), the GCF of the elements of set A is computed by repeatedly using the function h. The minimum number of times h is required to be used to compute G is : (CAT 1999)

• A. n
• B. (n - 1)
• C. n
• D. None of these

Answer 1

The correct option is B (n - 1)

It is clear that for n positive integers, function h (a,b) has to be used one time less than the number of integers, i.e. (n-1) times.