# uniquness proof

• Jul 14th 2009, 08:56 AM
matt23721
uniquness 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!
• Jul 14th 2009, 09:36 AM
Laurent
Quote:

Originally Posted by matt23721
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."

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 $\displaystyle a$ is a greatest element of a nonempty set $\displaystyle A$ (here, $\displaystyle A$ is the set of common divisors of two non-zero integers, it is nonempty since it contains 1). Then if $\displaystyle b$ is another greatest element, we would have both $\displaystyle a\geq b$ (because $\displaystyle a$ is larger than any element of $\displaystyle A$) and $\displaystyle b\geq a$ (because $\displaystyle b$ is larger than any element of $\displaystyle A$), hence $\displaystyle a=b$.
• Jul 14th 2009, 10:07 AM
pomp
The gcd of two integers, $\displaystyle x$ and $\displaystyle y$, is an integer $\displaystyle g$ satisfying

1. $\displaystyle g>0$
2. $\displaystyle g | x$ and $\displaystyle g | y$
3. If $\displaystyle z | x$and $\displaystyle z | y$ then $\displaystyle z | g$

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 $\displaystyle g$ and $\displaystyle \tilde{g}$ both satisfy properites 1, 2 and 3 above.

Then property 3 $\displaystyle \Rightarrow ~ g|\tilde{g}$ , $\displaystyle \tilde{g}|g ~ \Rightarrow ~ g = \pm \tilde{g}$

Property 1 $\displaystyle \Rightarrow ~ g,\tilde{g} > 0 ~ \Rightarrow ~ g = \tilde{g}$
• Jul 14th 2009, 04:53 PM
Jose27
Quote:

Originally Posted by Laurent
a "greatest" element of anything is always unique.

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'.
• Jul 14th 2009, 06:43 PM
matt23721
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
• Jul 14th 2009, 06:51 PM
pomp
Sorry if they didn't help, but both mine and Laurent's proofs were 'mathematical'. Was there something more you were looking for?
• Jul 14th 2009, 06:56 PM
matt23721
sorry i did not meant to sound rude! what i guess i meant to say is how to a go about showing its uniqueness
• Jul 14th 2009, 07:01 PM
pomp
Quote:

Originally Posted by matt23721
sorry i did not meant to sound rude! what i guess i meant to say is how to a go about showing its uniqueness

No worries.
Usualy in mathematics, if you're asked to prove something is unique, you assume it isn't. Then, you show that assuming this, you arrive at a contradiction.
This is what I did in my post when I assumed that $\displaystyle g$ and $\displaystyle \tilde{g}$ were both gcd's.
• Jul 14th 2009, 07:05 PM
matt23721
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??
• Jul 14th 2009, 07:08 PM
pomp
Quote:

Originally Posted by matt23721
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??

Yeh. You can call it shilrley if you want
• Jul 14th 2009, 07:14 PM
matt23721
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
• Jul 15th 2009, 02:48 PM
matt23721
hey pomp... real quick, whatd u mean by z where did that come from?
• Jul 15th 2009, 03:03 PM
pomp
Quote:

Originally Posted by matt23721
hey pomp... real quick, whatd u mean by z where did that come from?

z is just any old integer. So property 3 is just saying that if there is any old integer z, such that z divides both x and y, the z must also divide the gcd of x and y.
• Jul 15th 2009, 06:12 PM
matt23721
thanks man! i understand.... i sent u a message on fb