Greatest Common Divisor question?

prove that Greatest Common Divisor is unique

1 Answer

Relevance
  • ?
    Lv 4
    8 years ago

    I don't know what assumptions you are allowed to make.

    If you are allowed to assume that every number has a unique prime factorization, then it is easy to show that the gcd(a,b) is the product of prime factors that are common to a and b. For each such prime pi, if the prime factorization of a has a factor of pi^n and b has pi^n then the gcd will have pi with an exponent that is the minimum of m and n. It is then easy to show that any divisor of a and b must contain the same primes pi and that the exponent must be less than or equal to the exponent in the gcd.

    If you are finding the gcd using Euclid's algorithm, then from you know that the number g obtained from the algorithm is a divisor of a and b and satisfies an equation ax + by = g for some x and y. It is then easy to show that if d is any divisor of a and b, then from the equation it follows that d must also divide g. Let a = du and b=dv. Then dux + dvy = g. d(ux + vy) = g, so d divides g and so d <= g.

Still have questions? Get your answers by asking now.