Hello everyone, im having a little trouble on this problem...
"Show that greatest common divisor of two integers, which are not both
zero, is unique."
i came across this website: Greatest Common Divisors
any help would be aprreciated
thanks!
Hello everyone, im having a little trouble on this problem...
"Show that greatest common divisor of two integers, which are not both
zero, is unique."
i came across this website: Greatest Common Divisors
any help would be aprreciated
thanks!
That's a weird question: a "greatest" element of anything is always unique. It should seem obvious to you when you think of the set of the common divisors: this is a finite set of integers, it must have a greatest element, and I can't see how one may wonder if it is unique. Here's a proof anyway.
Suppose is a greatest element of a nonempty set (here, is the set of common divisors of two non-zero integers, it is nonempty since it contains 1). Then if is another greatest element, we would have both (because is larger than any element of ) and (because is larger than any element of ), hence .
The gcd of two integers, and , is an integer satisfying
- and
- If and then
While I'm not disagreeing with Laurent's proof, the property of 'greatest' can only be inferred from these.
As a more specific proof of the uniqueness of such an integer, let and both satisfy properites 1, 2 and 3 above.
Then property 3 ,
Property 1
Not true. In a ring (for example a unique factorization domain) in which you define a gcd (by the two last propierties pomp gave and that it be nonzero or a unit) this element is not unique since if we multiply it by a unit the new element is also a gcd, and there may not be an order that let's you decide which is 'the one'.