Define the gcd function for more than two arguments by the recursive equation gcd (a ₀ ,a ₁ …a _n ) = gcd (a ₀ , gcd(a ₁ ,a ₂ ,….a _n ). Show that the gcd function returns the same answer independent of the order in which its arguments are specified. Also show how to find integers x ₀ , x ₁ ….x _n such that gcd (a ₀ , a ₁ , … a _n ) = a ₀ x ₀ = a ₁ x ₁ + … + a _n x _n . Show that the number of divisions performed by your algorithm is O{n + lg(max{a _o ,a ₁ ,… a _n })).

Answer rating: 100% (QA)

The gcd of n1 integers can be defined by gcd function with n1 arguments as gcda 0 a 1 ... View the full answer