GCD and LCM Euclidean Algorithm in DSA Python - 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

Explain the Euclidean Algorithm for finding GCD.

The Euclidean Algorithm finds the GCD by repeatedly replacing the larger number with the remainder of dividing the larger by the smaller until the remainder is zero. The last non-zero remainder is the GCD.

intermediate

How is LCM related to GCD for two numbers a and b?

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 remainder becomes zero. At this point, the other number is the GCD.

intermediate

Why is the Euclidean Algorithm efficient for finding GCD?

It reduces the problem size quickly by replacing the larger number with a smaller remainder, avoiding checking all divisors. This makes it much faster than checking all possible divisors.

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

A 3

B 12

C 18

D 6

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

Which formula correctly relates LCM and GCD of two numbers a and b?

A LCM = GCD / (a × b)

B LCM = a + b - GCD

C LCM = (a × b) / GCD

D LCM = GCD × (a + b)

LCM(a, b) = (a × b) / GCD(a, b) is the correct formula.

In the Euclidean Algorithm, what do you do when the remainder is not zero?

A Replace the larger number with the remainder and repeat

B Replace the smaller number with the remainder and repeat

C Stop and return the remainder

D Add the remainder to both numbers

You replace the larger number with the remainder and continue until remainder is zero.

What is the GCD of two prime numbers?

A The smaller prime

B 1

C The larger prime

D Their product

Two different prime numbers have no common divisors except 1, so GCD is 1.

Why is the Euclidean Algorithm preferred over checking all divisors?

A It quickly reduces the problem size using remainders

B It uses addition instead of division

C It only works for small numbers

D It finds LCM directly

The algorithm reduces the problem size quickly by using remainders, making it efficient.

Describe step-by-step how to find the GCD of two numbers using the Euclidean Algorithm.

Think about repeatedly using division and remainder.

Explain how to calculate the LCM of two numbers using their GCD.

LCM and GCD are connected by a simple formula.