8.7.5. Proof of Euclid’s GCD Algorithm

Try these first

1. 1.

   What is the GCD of 15 and 25?

   Hint

   Find common factors of both numbers.

2. 2.

   Is 7 a prime number?

   Hint

   Check divisibility.

3. 3.

   What is the GCD of 48 and 18?

   • 12
   • 6
   • 24
   • 18

   Hint

   Remember to apply the division process.

4. 4.

   True or False: All prime numbers are odd except 2.

   • True
   • False

   Hint

   Recalling the definition of prime numbers.

5. 5.

   Prove Euclid's algorithm by using a counterexample to show that if GCD(a, b) is the same as GCD(b, r), then the algorithm will function correctly.

   Hint

   Consider specific values for a and b and their remainders to illustrate your point.

6. 6.

   Design an efficient algorithm to compute the GCD of 3 integers using the concept of pairwise GCD.

   Hint

   Use the associative property of GCD.