Re: GCD(0,0)
- From: Rufus.Zee@xxxxxxxxx
- Date: 29 Dec 2005 17:44:42 -0800
To define PID, we need to define some other terms beforehand; lets see.
BACKGROUND
---
A "semigroup" is a set G equipped with a binary operation * : G x G
-> G such that (a*b)*c = a*(b*c) [associativity].
A semigroup is said to be "abelian" iff a*b = b*a.
A "semigroup with identity" is a semigroup that has an element e called
the identity such that for every a, a*e = e*a = a.
A "group" is a semigroup with identity such that for every a in G,
there is a b in G such that a*b = e.
A group is said to be "abelian" iff a*b = b*a always; i.e. it is
abelian considered as a semigroup.
A "ring" is a set G equipped with two binary operators, + and *, such
that (G, +) is an abelian group, (G, *) is a semigroup, and the
distibutive law holds: a*(b + c) = a*b + a*c, and (a +b)*c = a*c +
b*c. for all a,b,c in G.
A ring is said to be "commutative" iff its multiplicative semigroup (G,
*) is abelian.
A "ring with identity" is a ring whose multiplicative semigroup (G, *)
has an identity.
Of particular interest are "commutative rings with identity."
An "integral domain" is a commutative ring with identity such that a*b
= 0 implies either a =0 or b =0. In other words, there are no zero
divisors.
Let X be an integral domain. An "ideal" in X is a subring S of X such
that for every x in X, every s in S, then xs is in S. (subring is easy
concept: S is a subring of X means that (S, +, *) is a ring when + and
* are restricted to S.)
Note that "ideals" can be defined for rings in general, not just
integral domains, however our goal is to define PID, and the above
suffices.
If a is an element of an integral domain X, the "principal ideal
generated by a" is the set consisting of all elements of the form ax,
for x in X. One can verify this really is an ideal. Any ideal that can
be realized in such a way is referred to as "principal."
A "principal ideal domain", or PID, is an integral domain in which
every ideal is principal.
The integers with + and * defined as usual comprise a PID. The ideals
are simply the sets that are {n a : n in Z }, i.e. multiples of some
number.
One may find a wikipedia entry for any of the quoted terms.
---
APPLICATION to GCD(a,b) DEFINITION
Any subset of an integral domain admits an ideal containing it; this is
clear since the entire ring is an ideal in itself. What is more, every
subset of an integral domain admits a smallest ideal containing it; to
see this, one convinces themselves that the intersection of arbitrarily
many ideals is again an ideal. Thus we can define (S), the ideal
generated by the set S, for any subset S of an integral domain, to be
the smallest ideal containing S.
In particular, we can generate ideals with two elements, say a and b,
defined to be the smallest ideal containing both a and b, denoted
(a,b). In a PID, every ideal is principal; so (a,b) = (c) for some c.
Of course c might not be determined uniquely; but if there is some way
of favoring a selection, we can define gcd(a,b) = c with that canonical
selection. This is what Silverman said above.
.
- References:
- GCD(0,0)
- From: Leroy Quet
- Re: GCD(0,0)
- From: JoeS
- Re: GCD(0,0)
- From: Carlos Moreno
- GCD(0,0)
- Prev by Date: Job: Chief Methodologist
- Next by Date: Re: GCD(0,0)
- Previous by thread: Re: GCD(0,0)
- Next by thread: Re: GCD(0,0)
- Index(es):
Relevant Pages
|
