8.7.2. Finding GCD using Prime Factorization

Try these first

1. 1.

   What is a prime number?

   Hint

   Think about its definition.

2. 2.

   Calculate the GCD of 24 and 36 using prime factorization.

   Hint

   First factor each number into primes.

3. 3.

   What is the definition of GCD?

   • The smallest number that can divide two numbers
   • The greatest number that can divide two numbers
   • Any number that divides two numbers

   Hint

   Think about the largest factor common to both.

4. 4.

   True or False: 28 is a prime number.

   • True
   • False

   Hint

   Remember the definition of prime number.

5. 5.

   If you were to compute the GCD of 210 and 45 using Euclid's Algorithm, what steps would you take?

   Hint

   Use the remainder at each step.

6. 6.

   Prove why every prime number is coprime to any integer that is not a multiple of itself.

   Hint

   Consider their definitions carefully.