250+ TOP MCQs on Euclid’s Algorithm and Answers

Data Structures & Algorithms Multiple Choice Questions on “Euclid’s Algorithm”.

1. 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

Answer: a
Clarification: 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. Who invented Euclid’s algorithm?
a) Sieve
b) Euclid
c) Euclid-Sieve
d) Gabriel lame
Answer: b
Clarification: Euclid invented Euclid’s algorithm. Sieve provided an algorithm for finding prime numbers. Gabriel lame proved a theorem in Euclid’s algorithm.

3. 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

Answer: c
Clarification: 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. Which of the following is not an application of Euclid’s algorithm?
a) Simplification of fractions
b) Performing divisions in modular arithmetic
c) Solving quadratic equations
d) Solving diophantine equations

Answer: c
Clarification: 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. 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

Answer: a
Clarification: 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. 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

Answer: a
Clarification: 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. 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

Answer: b
Clarification: 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. 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

Answer: a
Clarification: 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. 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)

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

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

Answer: a
Clarification: 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. 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)

Answer: a
Clarification: 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. What is the total running time of the binary GCD algorithm?
a) O(N)
b) O(N²)
c) O(log N)
d) O(N log N)

Answer: b
Clarification: Binary GCD algorithm is a sub division of Euclidean algorithm with more faster operations. Its running time is given by O(N²).

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

Answer: c
Clarification: GCD(m,n)=GCD(n, m mod n)
GCD(20,12)=GCD( 12,8)
= GCD(8,4)
= GCD(4,0) = 4.