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!

Printable View

- July 14th 2009, 09:56 AMmatt23721uniquness proof
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! - July 14th 2009, 10:36 AMLaurent
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 . - July 14th 2009, 11:07 AMpomp
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 - July 14th 2009, 05:53 PMJose27
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'.

- July 14th 2009, 07:43 PMmatt23721
thanks... starting to make some sense... how would i formulate that into a proof though? I sort of understand it in words... just writing it out in "math language" is a whole other story

- July 14th 2009, 07:51 PMpomp
Sorry if they didn't help, but both mine and Laurent's proofs were 'mathematical'. Was there something more you were looking for?

- July 14th 2009, 07:56 PMmatt23721
sorry i did not meant to sound rude! what i guess i meant to say is how to a go about showing its uniqueness

- July 14th 2009, 08:01 PMpomp
- July 14th 2009, 08:05 PMmatt23721
oh ok .. i follow you... instead of using g and g- could i use say one is g and the other "g" is say f??

- July 14th 2009, 08:08 PMpomp
- July 14th 2009, 08:14 PMmatt23721
haha thanks mate.. i appreciate it tons.. message me ur aim sn or facebook name if ud like, i might have a few questions later if u wouldnt mind helpn

- July 15th 2009, 03:48 PMmatt23721
hey pomp... real quick, whatd u mean by z where did that come from?

- July 15th 2009, 04:03 PMpomp
- July 15th 2009, 07:12 PMmatt23721
thanks man! i understand.... i sent u a message on fb