GCD and LCM Euclidean Algorithm in DSA C - Cheat Sheet & Quick Revision

Recall & Review

beginner

What does GCD stand for and what does it represent?

GCD stands for Greatest Common Divisor. It is the largest number that divides two or more numbers without leaving a remainder.

beginner

What is the Euclidean Algorithm used for?

The Euclidean Algorithm is a method to find the GCD of two numbers by repeatedly subtracting the smaller number from the larger one or using the remainder operation until the remainder is zero.

intermediate

How is LCM related to GCD?

LCM (Least Common Multiple) and GCD are related by the formula: LCM(a, b) = (a * b) / GCD(a, b). This means the product of two numbers equals the product of their GCD and LCM.

beginner

What is the base case in the Euclidean Algorithm for GCD?

The base case occurs when the second number becomes zero. At this point, the first number is the GCD.

intermediate

Why is the Euclidean Algorithm efficient compared to checking all divisors?

Because it uses division and remainder operations to reduce the problem size quickly, avoiding checking every possible divisor, which saves time especially for large numbers.

What is the GCD of 48 and 18 using the Euclidean Algorithm?

A 12

B 24

C 18

D 6

48 % 18 = 12, 18 % 12 = 6, 12 % 6 = 0, so GCD is 6.

Which operation is repeatedly used in the Euclidean Algorithm?

A Modulo (remainder)

B Subtraction

C Addition

D Multiplication

The Euclidean Algorithm uses modulo operation to find the remainder until it reaches zero.

If GCD(15, 20) = 5, what is LCM(15, 20)?

A 75

B 60

C 100

D 300

LCM = (15 * 20) / 5 = 300 / 5 = 60.

When does the Euclidean Algorithm stop?

A When both numbers are equal

B When the smaller number is zero

C When the remainder is zero

D When the larger number is zero

The algorithm stops when the remainder becomes zero.

Which of these pairs has a GCD of 1?

A 8 and 15

B 20 and 30

C 12 and 18

D 14 and 21

8 and 15 share no common divisors other than 1, so their GCD is 1.

Explain how the Euclidean Algorithm finds the GCD of two numbers step-by-step.

Think about dividing and taking remainders repeatedly.

Describe the relationship between GCD and LCM and how to calculate one if you know the other.

Remember the multiplication connection between GCD and LCM.