Reference no: EM132431022

Problem: We discuss the Euclidean algorithm that finds the greatest common divisor of 2 numbers u and v. We want to extend and compute the gcd of n integers gcd?(u_1,u_2,....u_n). One way to do it is to assume all numbers are non-negative, so if only one of if u_j≠0 it is the gcd. Otherwise replace u_k by u_k mod u_j for all k≠j where u_j is the minimum of the non-zero elements (u's). The algorithm can be made significantly faster if one consider the identity:gcd?(u_1,u_2....u_n )=gcd?(u_1,gcd?(u_2,u_3,..u_n )).

Then we may calculate gcd?(u_1,u_2....u_n ) with following algorithm:

Step 1. set d←u_n,j←n-1

Step 2. if d≠1 and j>0 set gcd?(u_j,d)and j=j-1 and repeat Step 2.

Else d=gcd(u_1,u_2,...u_n).

What is the smallest value of u_n such that the calculation of: gcd(u_1,u_2,...,u_n)

by steps Step 1 and Step 2 (given above) requires N divisions, if Euclid's algorithm is used throughout? Assume that N ≥ n.