Engineering Questions with Answers - Multiple Choice Questions

# Euclid’s Algorithm MCQ’s

1 - Question

Euclid’s algorithm is used for finding ___________
a) GCD of two numbers
b) GCD of more than three numbers
c) LCM of two numbers
d) LCM of more than two numbers

Explanation: Euclid’s algorithm is basically used to find the GCD of two numbers. It cannot be directly applied to three or more numbers at a time

2 - Question

Who invented Euclid’s algorithm?
a) Sieve
b) Euclid
c) Euclid-Sieve
d) Gabriel lame

Explanation: Euclid invented Euclid’s algorithm. Sieve provided an algorithm for finding prime numbers. Gabriel lame proved a theorem in Euclid’s algorithm.

3 - Question

If 4 is the GCD of 16 and 12, What is the GCD of 12 and 4?
a) 12
b) 6
c) 4
d) 2

Explanation: Euclid’s algorithm states that the GCD of two numbers does not change even if the bigger number is replaced by a difference of two numbers. So, GCD of 16 and 12 and 12 and (16-12)=4 is the same.

4 - Question

Which of the following is not an application of Euclid’s algorithm?
a) Simplification of fractions
b) Performing divisions in modular arithmetic
d) Solving diophantine equations

Explanation: Solving quadratic equations is not an application of Euclid’s algorithm whereas the rest of the options are mathematical applications of Euclid’s algorithm.

5 - Question

The Euclid’s algorithm runs efficiently if the remainder of two numbers is divided by the minimum of two numbers until the remainder is zero.
a) True
b) False

Explanation: The Euclid’s algorithm runs efficiently if the remainder of two numbers is divided by the minimum of two numbers until the remainder is zero. This improvement in efficiency was put forth by Gabriel Lame.

6 - Question

According to Gabriel lame, how many steps does Euclid’s algorithm require to solve a problem?
a) Less than five times the number of digits
b) More than five times the number of digits
c) Less than two times the number of digits
d) More than two times the number of digits

Explanation: The Euclid’s algorithm requires less than five times the number of digits. It runs by dividing two numbers. It stops when a remainder zero is reached.

7 - Question

Which of the following is the correct mathematical application of Euclid’s algorithm?
a) Determination of prime numbers
b) Lagrange’s four square theorem
c) Cauchy-Euler theorem
d) Residue theorem

Explanation: Lagrange’s four square theorem is one of the mathematical applications of Euclid’s algorithm and it is the basic tool for proving theorems in number theory. It can be generalized into other types of numbers like the Gaussian integers.

8 - Question

If GCD of two numbers is 1, then the two numbers are said to be ________
a) Co-prime numbers
b) Prime numbers
c) Composite numbers
d) Rational numbers

Explanation: If GCD of two numbers is 1, they are called as co-prime or relatively prime numbers. It does not mean that they are prime numbers. They don’t have any prime factors in common.

9 - Question

What is the total running time of Euclid’s algorithm?
a) O(N)
b) O(N log M)
c) O(N log N)
d) O(log N +1)

Explanation: The total running time of Euclid’s algorithm according to Lame’s analysis is found to be O(N).

10 - Question

Euclidean algorithm does not require the calculation of prime factors.
a) True
b) False

Explanation: Euclid’s algorithm does not require the calculation of prime factors. We derive the answer straight away using formula. And also, factorization is complex.

11 - Question

What is the formula for Euclidean algorithm?
a) GCD (m,n) = GCD (n, m mod n)
b) LCM(m,n)=LCM(n, m mod n)
c) GCD(m,n,o,p) = GCD (m, m mod n, o, p mod o)
d) LCM (m,n,o,p) = LCM (m, m mod n, o, p mod o)

Explanation: The formula for computing GCD of two numbers using Euclidean algorithm is given as GCD (m,n)= GCD (n, m mod n). It is used recursively until zero is obtained as a remainder.

12 - Question

What is the total running time of the binary GCD algorithm?
a) O(N)
b) O(N2)
c) O(log N)
d) O(N log N)

Explanation: Binary GCD algorithm is a sub division of Euclidean algorithm with more faster operations. Its running time is given by O(N2).

13 - Question

What is the GCD of 20 and 12 using Euclid’s algorithm?
a) 8
b) 2
c) 4
d) 6