Re: A gcd proposition

On Feb 28, 7:49 am, Dacong Yan <tonywinslow1...@xxxxxxxxx> wrote:
Hi, all!

I found a proof in Rotman's Abstract Algebra book that might be
problematic.

Corollary 1.33. Let a and b be integers. A non-negative common
divisor d is their gcd if and only if c | d for every common
divisor c.

Proof. Necessity (i.e., the implication =>) That every common
divisor c of a and b is a divisor of d = sa + tb, has already
been proved at the end of the proof of Theorem 1.32.
   Sufficiency (i.e., the implication <=) Let d denote the gcd
of a and b, and let d' be a non-negative common divisor divisible
by every common divisor c. Thus,d' <= d, because c <= d is for
every common divisor c. On the other hand, d itself is a common
divisor, and so d | d', by hypothesis. Hence, d <= d , and so
d = d'.

In the step to prove sufficiency, it did not prove the existence
of d'. Is it an obvious fact that "there exists a non-negative
common divisor divisible by every common divisor c"?


the => of the therrem is saying:

all common divisors divide the gcd (which is a nongegative common
divisor)

(*)So this direction tells you that there is at least one such
nonnegative common divisor with that special property (i.e., gcd).

-------------------------------------
the <= of the theorem is saying:

_IF_ there exists a nonnegative common divisor, say d, which is
divisible by any other common divisor, then d is the gcd.

(**)So this direction tells you that IF there is a nonnegative common
divisor with that special property, then it is the gcd (it does not
say such a thing exists)

-------------------------------------
So (*) said that gcd has that property, (**) says that the gcd is the
only one that "could possibly" have that property. So combined, it
says that the gcd has, and is the only one that has, that property.



.

Relevant Pages

  • Re: Common divisor, smaller than a delta
    ... does anyone knows if there is any method of calculating a 'common ... divisor' of n numbers, but this 'common divisor' must be smaller than a ... If s and t are the two real numbers, then the ratio ... you obtain approximating matrices ...
    (sci.math)
  • Re: A gcd proposition
    ... I found a proof in Rotman's Abstract Algebra book that might be ... A non-negative common ... divisor d is their gcd if and only if c | d for every common ... and let d' be a non-negative common divisor divisible ...
    (sci.math)
  • Re: A gcd proposition
    ... A non-negative common ... divisor d is their gcd if and only if c | d for every common ... and let d' be a non-negative common divisor divisible ... In the step to prove sufficiency, it did not prove the existence ...
    (sci.math)
  • Re: 請問如何用c語言寫一程式
    ... This program will figure out the greatest common ... divisor in two numbers you give. ... int first, second, nread; ... printf("The GCD is %d\n", (int) gcd_my); ...
    (comp.lang.c)
  • A gcd proposition
    ... A non-negative common ... divisor d is their gcd if and only if c | d for every common ... and let d' be a non-negative common divisor divisible ... In the step to prove sufficiency, it did not prove the existence ...
    (sci.math)