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 $\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$.
The gcd of two integers, $\displaystyle x$ and $\displaystyle y$, is an integer $\displaystyle g$ satisfying
- $\displaystyle g>0$
- $\displaystyle g | x$ and $\displaystyle g | y$
- 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}$
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'.
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.