8.7.3. Euclid’s GCD Algorithm

Try these first

1. 1.

   What is the GCD of 24 and 36?

   Hint

   Find the largest number that divides both 24 and 36.

2. 2.

   Are the numbers 9 and 28 co-prime?

   Hint

   Check their common divisors.

3. 3.

   What is the GCD of 15 and 10?

   • 5
   • 15
   • 10

   Hint

   List the factors of both numbers.

4. 4.

   True or False: The GCD of two numbers can be greater than either number.

   • True
   • False

   Hint

   Think about the definition of GCD.

5. 5.

   Using Euclid's algorithm, compute the GCD of 1071 and 462.

   Hint

   Perform divisions of 1071 by 462 and keep finding remainders until you reach 0.

6. 6.

   Prove that the GCD of a number and itself is the number.

   Hint

   Consider the definition of GCD.