Re: simple GCD question (but has me foxed)


Tim Peters wrote:
[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.

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


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" ?
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),
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).

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


.

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.

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.

.

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)
    ... Any integer that divides both x and y must also divide x-y, ... following the "gcd is the largest common divisor" definition you ... that both /sets/ of common divisors are exactly the same. ... Don't really care at this point. ...
    (sci.math)