8.7.4. Properties of GCD

Try these first

1. 1.

   What is the GCD of 20 and 30?

   Hint

   Look for the largest number that divides both.

2. 2.

   Is 12 a divisor of 36?

   Hint

   Divide 36 by 12.

3. 3.

   What is the GCD of 15 and 25?

   • 5
   • 15
   • 10

   Hint

   Think about common divisors.

4. 4.

   True or False: GCD(a, b) = GCD(b, a).

   • True
   • False

   Hint

   Consider how addition works.

5. 5.

   Find the GCD of 128 and 72 using Euclid's algorithm and explain each step taken.

   Hint

   Track remainders carefully.

6. 6.

   Using Lame's theorem, demonstrate that Euclid's algorithm is polynomial time by showing the number of iterations needed.

   Hint

   Link Fibonacci growth to logarithmic scales.