Re: x|m & x|n => x|gcd(m,n) ?

In article <dtumq2$qqd$1@xxxxxxxxxxxxxxxxx>,
kj <socyl@xxxxxxxxxxxxxxxxx> wrote:

[.snip.]

I realize, after the fact, that I had two distinct, somewhat
inconsistent, situations in mind when I posted my query. One, the
case of the integers, for which one could conceivably define gcd(m,n)
(where not both m and n are 0), as the positive integer d with the
property that d|m, d|n, and, for all integers x such that x|m and
x|n, it holds that x<=d.

Ugh. One reason I don't like this definition is that it does not make
sense in other settings: while all rings have the notion of
divisibility, few rings come with a ready-made order.

Another reason is that the "greatest" in "greatest common divisor" and
the "least" in "least common multiple" do not really refer to the
usual ordering of the integers, but rather to the (quasi)-ordering
through divisibility. In a ring, define an equivalence relation a~b if
and only if there exists a unit u such that a=ub (in the integers
this amounts to a~b if and only if a=b or a=-b); then you can define
an order on the set of classes by letting the class of a be "less than
or equl" to the class of b if and only if a|b. Under that ordering, 0
is the "greatest" integer, and {1,-1} is the "smallest".

With this definition, the result in the
subject line does not follow by definition.

Indeed, it would not. But you can get it by looking at the set (a,b)
just as I did.

The other situation
was the general case of a ring, not necessarily the integers, in
which case (as you confirmed) I suspected one could not assume a
unique factorization into primes.

Indeed not. "Primes" may not even make sense (in the algebraic
integers there are no primes at all); or factorization may not be
unique (in Z[sqrt(-5)], all of 2, 3, 1+sqrt(-5) and 1-sqrt(-5) are
'irreducible', meaning that if you can write them as a product then
one of the factors must be a unit, but 2*3 =
(1+sqrt(-5))(1-sqrt(-5)). They are not really "primes", though, since
that name is reserved for elements that satisfy the prime divisor
property (aka Euclid's Lemma: if p|ab then p|a or p|b). Every prime is
irreducible in any ring, but there may be irreducibles that are not
primes (as above, 2 is irreducible but not prime, since it divides
(1+sqrt(-5))(1-sqrt(-5)) but divides neither 1+sqrt(-5) nor
1-sqrt(-5)).

What I realize now is that the
definition I just gave for gcd is no good in the general case,
because in the general case there need not be an ordering.

Exactly. Better to define it through divisiblity. That does NOT
guarantee that the gcd is unique. In fact, in general it will not be,
and there will not be any good way of picking one over any other the
way we do with integers (by picking "the nonnegative one") or
polynomials over a field (by picking "the monic one").


--
======================================================================
"It's not denial. I'm just very selective about
what I accept as reality."
--- Calvin ("Calvin and Hobbes")
======================================================================

Arturo Magidin
magidin@xxxxxxxxxxxxxxxxx

.

Relevant Pages

  • Re: Rings of rationals
    ... intended definition of ring does not require a unit element. ... Let R be a unitary subring of Q. Then there exists a set A of primes, ... nonzero elements of R and let D=. ...
    (sci.math)
  • Re: Fundamental Theorem of Arithmetic
    ... heard so called - it is also known as the Unique Factorization ... but this was one of many in my Linear Algebra course in my first year at ... Primes are primes independent of the number base. ... your algebra book first proved it in the ring of polynomials ...
    (sci.math)
  • Re: abundance of irrationals!)
    ... >> Dik T. Winter wrote: ... >>> about primes you are talking about integers, ... If you have a set of things with arithmetic rules, ... >>> usual arithmetic, forms a ring. ...
    (sci.math)
  • Rings of rationals
    ... I posted the following conjecture: ... my intended definition of ring does not require a unit element. ... Every ring R of rationals can be categorized as follows: Let A be a set of primes. ... R = for some relatively prime integers r and s. ...
    (sci.math)
  • Re: SF: Back to theory
    ... the product of two primes. ... M, M/q = p ints in 0..M-1 in the same residue class as f mod q, and 1 int ... That's actually a bit less than the probability of picking a winning k ... finding f-g winners than picking f and g at random. ...
    (sci.math)