Math Is Fun Forum

JaneFairfax

Member

Registered: 2007-02-23

Posts: 6,868

Re: Euclidean Algorithm and GCD

Let’s generalize.

A nonempty subset I of

is called an ideal iff (i)

and (ii)

.

Note that condition (i) just says that I is an additive subgroup of

. Any ideal I contains 0 because if

(by definition I is nonempty),

. Also, if

, then

.

Theorem: I is an ideal of

if and only if there exists an integer d such that

.

We shall write

to denote the set

.

Proof: Verifying that

is an ideal is straightforward.

Conversely, suppose I is an ideal. If

, then

. Otherwise I must contain some positive integers, for if

, then

and one of

and

is positive. Then let d be the smallest positive member of I.

Since

for all

,

.

On the other hand, if

, we can write

where

and

. But then

and so, by minimality of d, we must have

. Hence

.

The above theorem is a particular case of a more general theorem, which is proved in an identical way to the above.

More general theorem: Every Euclidean domain is a principal-ideal domain.