179k views
2 votes
Using Euclidean algorithm find the greatest common divisor of 66 and 42

1 Answer

6 votes

Final answer:

Using the Euclidean algorithm, the greatest common divisor of 66 and 42 is found to be 6, determined through a series of divisions until a remainder of 0 is reached.

Step-by-step explanation:

To find the greatest common divisor (GCD) of 66 and 42 using the Euclidean algorithm, we repeatedly apply the basic step of the algorithm until we get a remainder of 0. Here is how it works:

  1. Divide 66 by 42 to get a quotient and a remainder. 66 = 42 × 1 + 24.
  2. Now take the previous divisor (42) and divide it by the remainder (24) from the first step. 42 = 24 × 1 + 18.
  3. Continue the process: divide 24 (previous remainder) by 18 (new remainder). 24 = 18 × 1 + 6.
  4. Now, divide 18 by the last remainder 6. 18 = 6 × 3 + 0. When we reach a remainder of 0, we stop the algorithm. The last non-zero remainder is the GCD. In this case, the GCD is 6.

Therefore, the greatest common divisor of 66 and 42 is 6.

User TOP KEK
by
7.5k points
Welcome to QAmmunity.org, where you can ask questions and receive answers from other members of our community.

9.4m questions

12.2m answers

Categories