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)

The question was asked in unit test.

I'm obligated to ask this question of Number Theory topic in chapter Number Theory of Data Structures & Algorithms II

Answer 1

The correct option is (a) GCD (m,n) = GCD (n, m mod n)

The best 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.