Using Euclidean Algorithm to Find GCD

Question:

How can we use the Euclidean algorithm to find GCD(1001, 1331)?

Answer:

To find the GCD of 1001 and 1331 using the Euclidean algorithm, divide the larger number by the smaller number and find the remainder. Continue dividing until the remainder is zero. The GCD is the last non-zero remainder.

Explanation:

The Euclidean algorithm is a method for finding the Greatest Common Divisor (GCD) of two integers. In this case, we want to find the GCD of 1001 and 1331.

Step 1: Divide 1331 by 1001. The division gives a quotient of 1 and a remainder of 330.

Step 2: Divide the previous divisor (1001) by the remainder (330). The division gives a quotient of 3 and a remainder of 11.

Step 3: Repeat the process by dividing 330 by 11. This division gives a quotient of 30 and a remainder of 0.

Since the remainder is now 0, the GCD of 1001 and 1331 is the last non-zero remainder, which is 11.