Re: A gcd proposition

Lax <Lax.Clarke@xxxxxxxxx> wrote:
On Feb 28, 7:49 am, Dacong Yan <tonywinslow1...@xxxxxxxxx> wrote:

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 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.

I.e. gcd may be defined implicitly as follows

c|(a,b) <=> c|a,b

Not only is this definition more general, but it often
yields simpler proofs, e.g. from one of my prior posts:

More generally and simply one may employ
these dual characterizations of GCD, LCM

n|a,b <=> n|(a,b) GCD

a,b|n <=> [a,b]|n LCM

Employing these yields a simple proof of

THEOREM (a,b) [a,b] = a b

PROOF a,b|n <=> ab| an,bn

<=> ab|(an,bn) by GCD

<=> ab|(a,b)n by gcd distributive law

<=> ab/(a,b)|n

Hence [a,b] = ab/(a,b) by LCM

One should compare this proof with many more awkward
proofs frequently presented in number theory textbooks.

Notice that this proof works in any gcd-domain,
which needn't be true if one uses more special
properties of Z, e.g. PID (via Bezout Identity).

This is extracted from my prior post in this thread
http://google.com/groups?threadm=y8z656r17be.fsf%40nestle.csail.mit.edu

See also my many prior posts on related topics, e.g.
http://google.com/groups/search?q=group:*math*+author:dubuque+gcd+lcm

--Bill Dubuque
.

Relevant Pages

  • Re: Simultaneous Equations
    ... and Y1 donot have a common factor n1. ... For real numbers a,b, a real number d is called a common divisor of a ... and b if d divides a and d divides b. ... Note that the above concept of divisibility for pairs of real numbers ...
    (sci.math)
  • Re: Simultaneous Equations
    ... and Y1 donot have a common factor n1. ... For real numbers a,b, a real number d is called a common divisor of a ... and b if d divides a and d divides b. ... Note that the above concept of divisibility for pairs of real numbers ...
    (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 ... all common divisors divide the gcd (which is a nongegative common ...
    (sci.math)
  • Re: English term for divisor
    ... common expression. ... as you can get to the related standard American English ... greatest common divisor, least common multiple. ...
    (sci.math)
  • Re: HISTORICAL CHALLENGE TO MR>ANDREW WILES ABOUT FLT
    ... > george ghiata wrote: ... >> Okay: ... >> 1).In case in which X and Y do not have a Common ... >> a common divisor with Y which implies X and Y have ...
    (sci.math)