# Euclid’s Algorithm Multiple choice Questions and Answers (MCQs)

## Euclid's Algorithm Multiple choice Questions and Answers (MCQs)

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

 Question 2
Who invented Euclid's algorithm?
 A Sieve B Euclid C Euclid-Sieve D Gabriel lame
Question 2 Explanation:
Euclid invented Euclid's algorithm. Sieve provided an algorithm for finding prime numbers. Gabriel lame proved a theorem in Euclid's algorithm.

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

 Question 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