Greatest Common Divisor

The greatest common divisor of two numbers is the largest number that evenly divides into both numbers.

  • If A = 0 then GCD(A, B)=B
  • If B = 0 then GCD(A, B)=A

Prime Factorization: GCD

Prime Factorization can be used to find the GCD of any two numbers. To do this you can multiply every prime factor of both numbers together. But if there are two factors with the same base keep the factor with the smallest power.

  • are all the prime bases of both numbers.
  • are the respective prime powers for the first number
  • are the respective prime powers for the second number
  • The minimum for each base is taken

For example:

  • So the GCD =
  • GCD =

Euclidean Algorithm

We can also use the Euclidean Algorithm for a more generalized strategy.