Re: simple GCD question (but has me foxed)

[Tim Peters]
...
Being very careful is what prompts it ;-) The sets S1 and S2 are in
fact
identical, but that's what you're trying to /prove/ -- you can't assume
it. From that S1 is a subset of S2, it does not follow that max(S1) =
max(S2), it only follows that max(S1) <= max(S2) (and min(S1) >=
min(S2),
but there's a reason nobody cares about the least common divisor ;-)).

[sttscitrans@xxxxxxxxx]
If you are being careful, aren't you assuming more about
the GCD, than the usual definition implies.

[Tim Peters]
I don't think so, but it's possible.

If a,b,c are integers, c is a gcd of a and b
iff c/a and c/b, and if d/a and d/b =>d/c


In Z, a gcd(12,-8) is 4 but also -4.

Which matches, e.g., the "some authors" definition given second on:

http://en.wikipedia.org/wiki/Greatest_common_divisor

[... stuff snipped ...]
That said, I did briefly consider "your" definition, but didn't mention
it because it seemed much more likely that the OP's instructor (or book)
was using "my" definition, both because that /is/ the one I've seen most
often, and because of the OP's statements like:

Any integer that divides both x and y must also divide x-y, so gcd(x;
y)
<= gcd(x - y; y).

Then why bring in " any integer" ?

I didn't write the OP's book, and I don't like its approach. That's why I
suggested a different (but related) approach to begin with. It sounds like
you don't like its approach either, but are asking me to defend it. Good
luck with that ;-)

However, following the "gcd is the largest common divisor" definition you
seem not to like either (but which I do like), the OP's book didn't consider
"any integer", but "any integer that divides both x and y". IOW, "any
common divisor". It seems natural to me to consider the set consisting of
all the common divisors if you're trying to reason about the largest element
in that set. Not compelling, not /necessary/, but natural enough.

gcd(x,y) is the biggest
integer which divides x and y, gcd(x,y) divides (x-y) so gcd(x,y)
divides gcd(x-y,y),

Which remains a slightly different approach than the one the OP was trying
to understand (unless you're straining to read his "<=" as "divides").

gcd(x-y,y) is the biggest integer which divides (x-y) and y.
gcd(x-y,y) must also divide x so gcd(x-y,y) divices x and y and so
divides gcd(x,y).

Ditto.

If a,b >0 and a divides b and b divides a then a =b
or
gcd(x-y,y)/gcd(x,y) >= 1
gcd(x,y)/gcd(x-y,y) >= 1

Which, if taken another step, finally reproduces the OP's:

gcd(x, y) <= gcd(x-y, y)
and
gcd(x-y, y) <= gcd(x, y)

but with more effort. Fine by me if you want to do it that way, but I don't
much care for it either. It seems more natural to me to reach the OP's
spelling directly by noting that max(S1) <= max(S2) is necessarily true of
any finite sets S1 and S2 of integers when S1 is a subset of S2.

BTW, note that reasoning in terms of sets of divisors gives the more
revealing (IMO) result that S1=S2. That is, it's not just that x & y,
and x-y & y, have the same /greatest/ common divisor, it's also the
case
that both /sets/ of common divisors are exactly the same.

This is necessary from the definition.

From the definition of gcd? It's certainly a necessary /consequence/ of
both gcd definitions, but neither definition talks about sets of divisors
directly.

The "ring" definition does refer to
common divisors other than a gcd.

Sure. But the definition (neither definition) does not state:

(*) the set of divisors of x & y is equal to the set of
divisors of and x-y & y

I have no idea what else the "this" in your "this is necessary from the
definition" could have been referring to. (*) is a /consequence/ of the
definitions. I take "necessary from the definition" to mean something much
more immediate than "can be proved". Maybe I just misunderstood you.

I don't think you can have it both ways.
If you are using the OP's definition then mentioning t
sets of common divisors seems superfluous.

Don't really care at this point. If you're claiming the proof using sets of
common divisors in incorrect, then I'd care. Else I remain happy with it
:-)


.

Relevant Pages

  • Re: GCD(0,0)
    ... >>>When it comes to common divisors, ... >>>divides 0, and otherwise an integer never divides ... I'll start it off with Sierpinski ... ...
    (sci.math)
  • Re: GCD(0,0)
    ... >>>When it comes to common divisors, ... >>>divides 0, and otherwise an integer never divides ... >>my point of view the G in GCD says it all. ... The usual Euclidean Algorithm applied to 0 and 0 would require dividing ...
    (sci.math)
  • Re: GCD(0,0)
    ... >>When it comes to common divisors, ... >>divides 0, and otherwise an integer never divides ... I'll start it off with Sierpinski ... ... Sierpinski, Elementary Theory of Numbers, 1964 ...
    (sci.math)
  • Re: simple GCD question (but has me foxed)
    ... That's an awkward proof. ... Any integer that divides two of these things ... So the set of _all_ common divisors x and y is the ... as the set of common divisors of x and x-y. ...
    (sci.math)
  • Re: simple GCD question (but has me foxed)
    ... the GCD, ... Any integer that divides both x and y must also divide x-y, ... that both /sets/ of common divisors are exactly the same. ...
    (sci.math)
Quantcast