# YOU CAN DOWNLOAD 200+ SUBJECTS PDF BOOK FOR COMPETITIVE EXAMINATIONS

## GCD and LCM using Recursion Multiple choice Questions and Answers (MCQs)

Question 11 [CLICK ON ANY CHOICE TO KNOW THE RIGHT ANSWER] |

If gcd (a, b) is defined by the expression, d=a*p + b*q where d, p, q are positive integers and a, b is both not zero, then what is the expression called?

Bezout's Identity | |

Multiplicative Identity | |

Sum of Product | |

Product of Sum |

Question 11 Explanation:

If gcd (a, b) is defined by the expression, d=a*p + b*q where d, p, q are positive integers and a, b is both not zero, then the expression is called Bezout's Identity and p, q can be calculated by extended form of Euclidean algorithm.

Question 12 [CLICK ON ANY CHOICE TO KNOW THE RIGHT ANSWER] |

Is gcd an associative function.

True | |

False |

Question 12 Explanation:

The gcd function is an associative function as gcd (a, gcd (b, c)) = gcd (gcd (a, b), c).

Question 13 [CLICK ON ANY CHOICE TO KNOW THE RIGHT ANSWER] |

Which is the correct term of the given relation, gcd (a, b) * lcm (a, b) =?

|a*b| | |

a + b | |

a - b | |

a / b |

Question 13 Explanation:

The gcd is closely related to lcm as gcd (a, b) * lcm (a, b) = |a*b|.

Question 14 [CLICK ON ANY CHOICE TO KNOW THE RIGHT ANSWER] |

Who gave the expression for the probability and expected value of gcd?

James E. Nymann | |

Riemann | |

Thomae | |

Euler |

Question 14 Explanation:

In the year 1972, James E. Nymann showed some result to show the probability and expected value of gcd.

Question 15 [CLICK ON ANY CHOICE TO KNOW THE RIGHT ANSWER] |

What is the computational complexity of Binary GCD algorithm where a and b are integers?

O (log a + log b) ^{2}) | |

O (log (a + b)) | |

O (log ab) | |

O (log a-b) |

Question 15 Explanation:

From the Binary GCD algorithm, it is found that the computational complexity is O (log a + log b)

^{2}) as the total number of steps in the execution is at most the total sum of number of bits of a and b. There are 15 questions to complete.