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
View Answer
Answer: a
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
View Answer
Answer: b
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
View Answer
Answer: c
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
c) Solving quadratic equations
d) Solving diophantine equations
View Answer
Answer: c
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
View Answer
Answer: a
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
View Answer
Answer: a
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
View Answer
Answer: b
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
View Answer
Answer: a
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)
View Answer
Answer: a
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
View Answer
Answer: a
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)
View Answer
Answer: a
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)
View Answer
Answer: b
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
View Answer
Answer: c
Explanation: GCD(m,n)=GCD(n, m mod n)
GCD(20,12)=GCD( 12,8)
= GCD(8,4)
= GCD(4,0) = 4.