Kezdőlap


Cím:	Megjegyzések a C.461. gyakorlat ürügyén
Szerző(k):	Fried Ervin
Füzet:	1997/november, 473 - 480. oldal	PDF \| MathML
Témakör(ök):	Szakmai cikkek
Hivatkozás(ok):	Feladatok: 1997/március: C.461

A szöveg csak Firefox böngészőben jelenik meg helyesen. Használja a fenti PDF file-ra mutató link-et a letöltésre.

A feladat annak a bizonyítása volt, hogy a $\frac{21 n + 4}{14 n + 3}$ tört egyetlen $n$ egész szám esetén sem egyszerűsíthető.^*
Egy tört egyszerűsíthetősége azon múlik, hogy mi a számláló és a nevező legnagyobb közös osztója. A gondot az jelenti, hogy egy ,,változó'' szám is szerepel. Ennek következtében lehet, hogy bizonyos esetekben nincs 1-től különböző közös osztó, máskor meg van.
Mindenekelőtt gondoljuk végig, miképpen lehet két szám legnagyobb közös osztóját meghatározni. Erre a legjobb és leggyorsabb módszer az úgynevezett Eukideszi algoritmus, amelyik a maradékos osztáson alapszik. A maradékos osztás a következőképpen szól:
Ha adott az $a$ és a $0$ -tól különböző $b$ egész szám, akkor mindig léteznek olyan $q$ és $r$ egész számok, hogy $| r | < | b |$ , és fennáll az $a = q \cdot b + r$ egyenlőség.
Maga a felírt egyenlőség igen érzékeny a legnagyobb közös osztóra (mindjárt kiderül mely számokéra). Tegyük fel, hogy $d$ osztója $a$ -nak és $b$ -nek: $a = d \cdot a_{1}$ és $b = d \cdot b_{1}$ . Ekkor $r = d \cdot (a_{1} - q \cdot b_{1})$ , azaz $d$ $b$ -nek és $r$ -nek is közös osztója. Ha viszont $d_{1}$ a $b$ -nek és az $r$ -nek közös osztója, azaz $b = d_{1} \cdot b_{2}$ és $r = d_{1} \cdot r_{2}$ , akkor $a = d_{1} \cdot (q \cdot b_{2} + r_{2})$ . Eszerint az $(a, b)$ pár közös osztói ugyanazok, mint a $(b, r)$ pár közös osztói. Ez a megállapítás természetesen nem függ attól, hogy léteznek-e legnagyobb közös osztók.
Ha most a maradékos osztást a $b$ és $r$ számokra végezzük el, akkor a kapott $r_{1}$ maradékra ismét teljesül az $| r_{1} | < | r |$ ; továbbá az is, hogy az $(r, r_{1})$ pár osztói megegyeznek a $(b, r)$ pár osztóival; és így ugyanazok, mint az eredeti $(a, b)$ pár osztói. Mivel pozitív egészek csökkenő sorozata csak véges lehet, ezért az eljárás egyszer véget ér. A legvégül kapott maradékra csak 0 adódhat. Az előző maradékot jelölje $r_{s + 1}$ . Ekkor ennek és 0-nak a közös osztói ugyanazok, mint az $(a, b)$ párnak. Tekintettel arra, hogy 0-nak minden szám osztója, ezért $r_{s + 1}$ lesz a két adott szám legnagyobb közös osztója.
Az eljárás során még valami öröklődik lépésról lépésre. Az első két szám felírható, mint $a$ és $b$ úgynevezett egész együtthatós lineáris kombinációja: $a = a \cdot 1 + b \cdot 0$ és $b = a \cdot 0 + b \cdot 1$ . Ez a tulajdonság is végig öröklődik. Ha valamelyik két maradék ( $b$ a ,,nulladik" és $a$ a ,,mínusz egyedik" maradék) ilyen alakú, akkor a következő is ilyen alakú lesz. Legyen $r_{t - 1} = a x_{t - 1} + b y_{t - 1}$ és $r_{t} = a \cdot x_{t} + b \cdot y_{t}$ . Az $r_{t - 1} = q_{t} r_{t} + r_{t + 1}$ összefüggésből:

\begin{matrix} r_{t + 1} = a \cdot x_{t - 1} + b \cdot y_{t - 1} - q_{t} (a \cdot x_{t} + b \cdot y_{t}) = a \cdot (x_{t - 1} - q_{t} x_{t}) + b \cdot (y_{t - 1} - q_{t} y_{t}) \end{matrix}

adódik; ami éppen a kívánt alakú felírás.
Megjegyezzük, hogy hasonló eljárás létezik például racionális vagy valós együtthatós polinomok esetében is: adott

f (x)

és 0-tól különböző

g (x)

polinomokhoz létezik olyan

q (x)

és

r (x)

polinom, amelyekre

f (x) = q (x) g (x) + r (x)

, de itt nem az abszolút érték, hanem a fokszám csökken az eljárás lépéseiben:

gr (r (x)) < gr (g (x))

, vagy

r (x) = 0

, az azonosan 0 polinom. (Ez utóbbira azért van szükség, mert az azonosan 0 polinomnak nincs foka.)
Ezt az eljárást nevezik Euklideszi algoritmusnak. Ennek eredményeként azt láttuk be, hogy az

a

és

b

egész számok

d

legnagyobb közös osztóját

d = a x + b y

alakba írhatjuk.
Az általában igaz, hogy

a x + b y

mindig osztható

a

és

b

minden közös osztójával. Ha azonball nem ,,konkrét" számokról van szó, akkor nem feltétlen kapjuk meg a legnagyobb közös osztót. Eredeti példánkban

21 n + 4

és

14 n + 3

legnagyobb közös osztóját kerestük.

1 = 3 (14 n + 3) - 2 (21 n + 4)

miatt ez csak 1 lehet.
Kiindulási példánk helyett vegyük az

n

-et és 2-t. Egy

n x + 2 y

alakú szám csak úgy lehet tetszőleges

n

mellett osztója 2-nek, ha

x = 0

. Egy

2 y

alakú szám viszont nem lehet tetszőleges

n

esetén az

n

osztója (például az

n = 1

esetben sem). Mégis, azt meg tudjuk mondani, hogy minden

n

-re csak 1 lehet közös osztó, míg páros

n

-re 2 a legnagyobb közös osztó. Persze itt csak azért lett minden viszonylag egyszerűbb, mert a két kiindulási szám is elég egyszerű volt. Általában egész

a

b

c

d

mellett kell keresni az

a n + b

és

c n + d

legnagyobb közös osztóját. A

c (a n + b) - a (c n + d) = c b - a d

összefüggésből azonnal látszik, hogy a legnagyobb közös osztó mindig osztója

(b c - a d)

-nek is. Nem biztos azonban, hogy e szám minden osztója közös osztó. Az eredeti példa alapján is látható, hogy itt ,,túl nagy" számokkal szoroztunk. Célszerűbb az

a

és

b

legnagyobb közös osztójától eltekinteni. Ennek megfelelően az alábbi kiindulást érdemes tekinteni: Legyen a két szám

A = a u n + b v

és

C = c u n + d v

, ahol

a

és

c

, valamint

b

és

d

relatív prímek (nincs 1-tó1 különböző pozitív osztójuk). Ekkor

A

-nak és

C

-nek minden közös osztója osztja a

c A - a C = (c b - a d) v = V

számot.
Jó lenne most emellé a

V

szám mellé egy olyan

U

számot találni, hogy

U

és

V

közös osztói megegyezzenek

A

és

C

közös osztóival. Ilyen számot találhatunk!
Mivel

a

és

c

legnagyobb közös osztója 1, azért ennek a lineáris kombinációként való előállíthatósága alapján vannak olyan

x

és

y

egész számok, amelyekre

a x - c y = 1

. Azt állítjuk, hogy megfelelő lesz az ezekkel képzett

U = x A - y C

szám. Természetesen

A

és

C

minden közös osztója

U

-nak is osztója. A

c U - x V = (- c y + a x) C = C

, valamint az

a U - y V = (a x - c y) A = A

összefüggések alapján

U

és

V

valóban megfelelnek a kívánalmaknak.

U

-t kiszámítva az

U = x (a u n + b v) - y (c u n + d v) = u n + (b x - d y) v

egyenlőséghez jutunk. Még abban is ,,szerencsénk van", hogy

n

együtthatója az eredeti két együttható legnagyobb közös osztója.
Az

e = c b - a d

és

f = b x - d y

jelöléssel tehát feladatunk az

u n + f v

és az

e v

számok legnagyobb közös osztójának a meghatározása. Vegyük azonban észre, hogy

e

és

f

nem teljesen függetlenek egymástól. Fennállnak ugyanis a

c f - x e = - d c y + d a x = d

és

a f - y e = a b x - y c b = b

összefüggések. Eszerint

e

és

f

minden közös osztója

b

-nek és

d

-nek is közös osztója lesz. Mivel ezek relatív prímek, azért

e

és

f

is relatív prímek.
Tehát az

u n + f v

és az

e v

számok legnagyobb közös osztóját keressük, ahol

e

és

f

relatív prímek.
Ha itt az

u

és

v

számok legnagyobb közös osztója 1-nél nagyobb, akkor ez természetesen mindig közös osztó lesz. A kérdés az, hogy lesz-e mindig vagy néha ennél nagyobb közös osztó is. Ennek megállapítása céljából egyszerűsítsünk

u

és

v

legnagyobb közös osztójával, és az ezután keletkező számokat vizsgáljuk. Tulajdonképpen így egy olyan esethez jutunk el, amelyikben az

u

és

v

is relatív prímek.
Az első kérdés most már az, hogy lehet-e az

u n + f v

és az

e v

számoknak

n

-től független 1-nél nagyobb közös osztója. Ennek lehetetlenségét elég úgy megmutatni, hogy az

n = 0

és az

n = 1

esetet nézzük meg. A figyelembe veendő három szám

e v

f v

és

u + f v

. Az

e v

és

f v

számok legnagyobb közös osztója

v

. Ennek és

(u + f v)

-nek minden közös osztója az

(u + f v) - f \cdot (v) = u

számnak is osztója. Tekintettel arra, hogy

u

és

v

relatív prímek, tehát nem létezik 1-nél nagyobb közös osztó.
A második kérdés az, hogy lehet-e ,,néha" 1-nél nagyobb közös osztójuk. Amennyiben

| v | \neq 1

, akkor például az

n = k v

esetben

u n + f v

is osztható

v

-vel, tehát végtelen sok ilyen számnak van 1-nél nagyobb közös osztója. Nézzük most a

v = 1

esetet (a

v = - 1

eset teljesen hasonló). A vizsgált számok az

u n + f

alakúak, valamint az

e

.
Két esetet különböztetünk meg. Tegyük fel először, hogy

e

-nek minden prímosztója osztója

u

-nak is. Ha volna valamilyen

n

esetén az

u n + f

és az

e

számoknak 1-nél nagyobb közös osztója, akkor volna közös osztója, amely persze osztója lenne

e

-nek; és feltételünk szerint

u

-nak is. Ekkor viszont osztója lenne

u n

-nek és így az

f = (u n + f) - u n

számnak is, ami lehetelen, mert

f

és

e

relatív prímek. Ebben az esetben tehát soha sincs 1-nél nagyobb közös osztó.
A másik lehetőség az, hogy van az

e

-nek olyan

p

prímosztója, amelyik nem osztja

u

-t. Ebben az esetben

u

és

p

relatív prímek, tehát léteznek olyan

x

és

y

egész számok, amelyekre

u x + p y = 1

teljesül. Nézzük most tetszőleges

k

egész szám mellett az

n = p k - f x

számokat. Ezekre

u n + f = u p k - u f x + f = u p k - f (1 - p y) + f = u p k + f p y = p (u k + f y)

ugyancsak osztható

p

-vel tehát ezeknek és

e

-nek a legnagyobb közös osztója nagyobb mint 1. Tekintettel arra, hogy

u (p k - f x) + f

alakú szám végtelen sok van, míg

e

osztóinak a száma véges, ezért biztosan található végtelen sok olyan

n

, amelyekre

u n + f

és

e

legnagyobb közös osztója ugyanaz az 1-nél nagyobb szám.
Tulajdonképpen az egész bonyodalomnak a hátterében az egész együtthatós polinomok viselkedése van.
Tetszőleges

S

számkörbeli együtthatós polinomok

a_{0} + a_{1} x + a_{2} x^{2} + ... + a_{n} x^{n}

alakú formális kifejezések, ahol az

a_{0}

a_{1}

a_{2}

...

a_{n}

együtthatók az adott

S

számkörből valók, és nem minden együttható 0. Ha

a_{n} \neq 0

, akkor a polinomot

n

-edfokúnak nevezzük; és

a_{n}

neve a polinom főegyütthatója. Az

S

számkörről feltesszük, hogy nem üres; és zárt az összeadásra, kivonásra és a szorzásra. A polinomok ,,készen állnak arra", hogy az

x

határozatlan helyébe egy számot írjunk. Ennek megfelelően úgy számolhatunk velük, mintha

x

szám volna. Az együtthatókat leggyakrabban a racionális számok

Q

, vagy a valós számok

R

halmazából vesszük. Így vannak racionális vagy valós együtthatós polinomok, amelyek körében (mint említettük) elvégezhető a maradékos osztás; ezért az euklideszi algoritmus is. Ennek megfelelően létezik bármely két polinomnak legnagyobb közös osztója (ami azt jelenti, hogy olyan közös osztó, amely minden közös osztónak többszöröse). Ennek következménye az, hogy minden legalább elsőfokú polinom felírható tovább már nem bontható legalább elsőfokú polinomok szorzatára; és ez a felbontás lényegében egyértelmű. (Ezeknek a fogalmaknak a precíz tárgyalása túl messzire vezetne; maradjunk meg annál, amit könnyen elképzelhetünk.) Ezt úgy mondjuk, hogy érvényes az egyértelmű faktorziáció.
Beszélhetünk egész együtthatós polinomokról is. Nem meglepő, de elég nehezen bizonyítható, hogy ezek körében is érvényes az egyértelmű faktorizáció. Hasonló a helyzet többhatározatlanú polinomok esetében is.
A nehézségnek az az oka, hogy a legnagyobb közös osztó nem mindig írható fel ,,lineáris kombináció alakban". (Ebből persze következik, hogy nem is létezhet euklideszi algoritmus.) Tekintsük például az

x

és a 2 egész együtthatós polinomokat. Legyen

d (x)

ezeknek legnagyobb közös osztója, és tegyük fel, hogy felírható lineáris kombinációként:

d (x) = f (x) \cdot x + g (x) \cdot 2

. A jobb oldalon egy olyan polinom áll, amelynek a konstans tagja páros. Mivel

d (x)

osztója 2-nek (az egész együtthatós polinomok körében!), azért

d (x)

csak konstans lehet; amely ráadásul 2-nek az egész számok körében osztója, azaz vagy 2, vagy

- 2

. Ezt viszont bármely egész együtthatós polinommal szorozzuk is meg, mindig olyan polinomot kapunk, amelynek együtthatói párosak; tehát ennek nem többszöröse az

x

polinom.
Hasonlóképpen látható be, hogy az

x

és

y

határozatlanok racionális együtthatós polinomjai között az

x

és

y

polinomok legnagyobb közös osztója nem állítható elő ezek lineáris kombinációjaként.
A lineáris kombinációként való előállíthatóság igen fontos tulajdonság. Tekintsük az egész együtthatós polinomok

Z [x]

összességét; beleértve az összeadás (kivonás) és szorzás műveletét. (

R

jelöli az egész számok összességét a szokásos műveletekkel, és

x

jelöli a határozatlant.) Ennek egy

I

(nem üres) részhalmazát ideálnak nevezzük, ha zárt a

Z [x]

-beli lineáris kombinációra; azaz tetszőleges

f (x)

g (x) \in I

és

u (x 0

v (x) \in Z

esetén

u (x) f (x) | v (x) g (x) \in I

.
Könnyű belátni, hogy minden

I

ideálra teljesülnek az alábbiak:
(1)

0 \in I

,
(2) ha

f (x)

g (x) \in I

, akkor

f (x) + g (x)

f (x) - g (x) \in I

,
(3) Ha

f (x) \in I

és

u (x) \in Z [x]

, akkor

u (x) f (x) \in I

.
Triviális, hogy az egyedül 0-ból álló halmaz, valamint az egész

Z [x]

ideálok.

Z [x]

-beli ideálokra igen fontos példa egyetlen

f (x)

polinom

Z [x]

-beli polinomokkal való szorzata (az

{u (x) f (x)}

polinomhalmaz, ahol

u (x)

végigfut

Z [x]

elemein). Az

f (x) = 0

és az

f (x) = 1

esetben éppen az előbb felírt két triviális ideált kaptuk.
Vannak azonban más ideálok is. Ugyancsak könnyű belátni, hogy tetszőlegesen adott

f_{1} (x)

...

f_{n} (x)

esetében az

u_{1} (x) f_{1} (x) + ... + u_{n} (x) f_{n} (x)

alakú polinomok ‐ ahol az

u_{1} (x)

...

u_{n} (x)

polinomok egymástól függetlenül végigfutnak a

Z [x]

elemein ‐ mindig egy ideált alkotnak. Ezt az ideált az

f_{1} (x)

...

f_{n} (x)

generálta ideálnak nevezzük; és az

f_{1} (x)

...

f_{n} (x)

polinomhalmazt ezen ideál egy generátorrendszerének. Természetesen egy ideálnak több generátorrendszere is lehet. A fenti ideált

(f_{1} (x), ..., f_{n} (x))

fogja jelölni.
Ha csak egyetlen polinomot tekintünk, akkor éppen az előbb megadott példákat kapjuk. Az egyetlen elem által generált ideál neve főideál.
Ezek a fogalmak ‐ megfelelően ‐ kialakíthatók az egész számok körében. Könnyű belátni, hogy az euklideszi algoritmus következménye az, hogy ott minden ideál főideál. Ez annak a ténynek az átfogalmazása, hogy bármely két egész szám legnagyobb közös osztója előállítható ezek egész együtthatós lineáris kombinációjaként.
Az előzőekben megmutattuk, hogy az egész együtthatós polinomok körében ez nem igaz; nevezetesen az

(x, 2)

ideál nem főideál. A továbbiakban belátjuk, hogy a helyzet még ennél is ,,rosszabb":

1. Tétel. Minden

n

természetes számhoz található

Z [x]

-ben olyan

I_{n}

ideál, amely nem generálható

n

-nél kevesebb elemmel.
Azt is be fogjuk látni, hogy azért a helyzet nem ,,végtelenszer rosszabb", ugyanis igaz az alábbi:

2. Tétel. Minden

Z [x]

-beli

I

ideálhoz létezik olyan

n_{I}

természetes szám, hogy

I

generálható

n_{I}

számú elemmel.
Érdemes megjegyezni, hogy hasonló a helyzet a racionális vagy valós együtthatós kéthatározatlanú polinomok esetében is (még a bizonyítás is hasonlóképpen történhet). Sőt, mi több, három, négy stb. határozatlan esetében is hasonló eredmény igaz; a 2. Tétel bizonyítása viszont lényegesen bonyolultabb. Ha viszont a határozatlanok száma végtelen, akkor a 2. Tétel nem igaz: könnyen be lehet látni, hogy azok a polinomok, amelyeknek a konstans tagja 0, egy ideált alkotnak; és ez az ideál nem generálható véges sok elemmel.
A bizonyítás előtt előrebocsátunk néhány dolgot:

1. Állítás. Mint már láttuk, ha

d

a d

és

b d

egész számok legnagyobb közös osztója, akkor vannak olyan

p

és

q

egész számok, amelyekre

a d p + b d q = d

, illetve

a p + b q = 1

A rövidebb jelölés kedvéért, ha nem konkrét polinomokról van szó, akkor ezeket nagy betűkkel fogjuk jelölni. Így az

(F_{1}, ..., F_{n})

ideál elemei az

U_{1} F_{1} + ... + U_{n} F_{n}

polinomok.

2. Állítás.

I = (F_{1}, ... F_{n})

az a legkisebb ideál, amely e polinomok mindegyikét tartalmazza.
Ha egy

J

ideál tartalmazza ezeket a polinomokat, akkor tartalmazza ezek lineáris kombinációt is, tehát

I

-t. Másrészt tetszőleges

i

indexre legyen

U_{i} = 1

és minden más

j

indexre

U_{j} = 0

. Ekkor az ezekkel képezett lineáris kombináció pontosan

F_{i}

; így az adott polinomok mindegyike eleme

I

-nek.

3. Állítás. Ha

a

b

relatív prím egészek és a

p

q

egészekre

a p + b q = 1

, akkor az

U = a F + b G

és

V = q F - p G

polinomokra

\begin{matrix} (F, G, H_{1}, ..., H_{n}) = (U, V, H_{1}, ..., H_{n}) . \end{matrix}

A 2. Állítás alapján elég azt belátni, hogy a generátorelemek mindegyike eleme a másik ideálnak. Csak az első két polinommal kell foglalkozni, mert a többiek mindkét ideálban benne vannak.

U

V \in (F, G, H_{1}, ..., H_{n})

nyilvánvaló.

F = p U + b V

és

G = q U - a V

alapján

F

G \in (U, V, H_{1}, ..., H_{n})

is igaz.

Mivel

a = 1

és tetszóleges

b

relatív prímek, azért ezekhez található alkalmas

p

és

q

; valóban

p = 1

és

q = 0

megfelelők. Ebben az esetben

U = F + b G

és

V = - p G

(illetve

V = p G

) megfelelőek. Ez a speciális eset

b

helyett tetszőleges

B

polinomra is átvihető:

4. Állítás. Tetszőleges

B

polinom esetén az

U = F + B G

polinomra

\begin{matrix} (F, G, H_{1}, ..., H_{n}) = (U, G, H_{1}, ..., H_{n}) . \end{matrix}

A 3. Állításhoz hasonlóan itt is minden igaz, csak azt kell még belátni, hogy

F \in (U, G, H_{1}, ..., H_{n})

. Ez viszont következik az

F = U - B G

összefüggésből.

a

b

egész számok legnagyobb közös osztóját

(a, b)

szokta jelölni. Nem baj, ha ezt ,,összetévesztjük" az ideál-jelöléssel, mert, ha

d

a legnagyobb közös osztó, akkor éppen az

(a, b) = (d)

ideál egyenlőséget kapjuk.
Az

a_{1}

...

a_{n}

egész számok legnagyobb közös osztóját

(a_{1}, ..., a_{n})

jelöli.

5. Állítás. A legnagyobb közös osztó képzése ,,asszociatív", azaz

(a_{1}, ..., a_{n}, a_{n + 1}) = ((a_{1}, ..., a_{n}), a_{n + 1})

. Az

a_{1}

...

a_{n}

egész számok legnagyobb közös osztóját elő tudjuk állítani

n - 1

lépésben úgy, hogy mindig egy már megkapott legnagyobb közös osztónak és a következő egész számnak relatív prím egész együtthatókkal képezett lineáris kombinációját vesszük.
Az első állítás azonnal következik abból, hogy

d

pontosan akkor osztója a fenti

n + 1

számnak, ha az első

n

számnak osztója, és ezen kívül az

(n + 1)

-ediknek is. A második állítást teljes indukcióval igazoljuk. Az

n = 2

eset az 1. Állítás szerint igaz. Tegyük fel, hogy az állítás igaz

n

-re, és legyen

d_{n} = (a_{1}, ..., a_{n})

. Az 5. Állítás első része szerint

d_{n + 1} = (a_{1}, ..., a_{n}, a_{n + 1}) = (d_{n}, a_{n + 1})

. Az 1. Állítás alapján viszont ehhez léteznek olyan relatív prím

p

és

q

egész számok, amelyekre

d_{n + 1} = p d_{n} + q a_{n + 1}

6. Állítás. Legyen

d = (a_{1}, ..., a_{k})

, és tekintsük az

I = (F_{1}, ..., F_{n})

ideált, ahol

k < n

. Ekkor léteznek olyan

p_{1}

...

p_{k}

egész számok, hogy

d = p_{1} a_{1} + ... + p_{k} a_{k}

, és

I

-nek van olyan

G_{1}

...

G_{n}

generátorrendszere, amelyre

G_{1} = p_{1} F_{1} + ... + p_{k} F_{k}

.
Alkalmazzuk az 5. Állításban leírt eljárást az adott

a_{1}

...

a_{k}

számokra. Ugyanezt az eljárást elvégezhetjük az adott polinomokra is. Az első lépésben

d_{2} = p a_{1} + q a_{2}

. A 3. Állítás szerint a

H_{1} = p F_{1} + q F_{2}

és alkalmas

a'

b'

egészekkel képezett

G_{2} = a' F_{1} + b' F_{2}

polinomokra

I = (H_{1}, G_{2}, F_{3}, ..., F_{n})

. Most folytatjuk az eljárást

d_{2}

-vel és

a_{3}

-mal párhuzamosan

H_{1}

-re és

F_{3}

-ra. Ezeket helyettesítve egy

H_{2}

G_{2}

G_{3}

F_{4}

...

F_{n}

generátorrendszert nyerünk. Az utolsó lépésként kapott

G_{1} = H_{k - 1}

polinom pontosan úgy lett előállítva az

F_{1}

...

F_{k}

polinomokból, mint

d

a_{1}

...

a_{k}

számokból. Mivel

G_{1}

...

G_{k}

G_{k + 1}

...

F_{k}

is generátorrendszer, azért az állítás valóban igaz.

Az 1. Tétel bizonyítása. Tekintsük az

\begin{matrix} I = {2^{n}, 2^{n - 1} x, 2^{n - 2} x^{2}, ..., 2^{2} x^{n - 2}, 2 x^{n - 1}, x^{n}} \end{matrix}

ideált. Azt fogjuk megmutatni, hogy

n

darab polinommal nem generálható az

I

ideál.
Mivel egy ideál elemei a generátorelemek polinomegyütthatós lineáris kombinációi, azért

I

elemei pontosan az

\begin{matrix} a_{n} 2^{n} + a_{n - 1} 2^{n - 1} x + a_{n - 2} 2^{n - 2} x^{2} + ... + a_{2} 2^{2} x^{n - 2} + a_{1} 2 x^{n - 1} + F x^{n} \end{matrix}

alakú polinomok, ahol

a_{n}

...

a_{1}

tetszőleges egész számok és

F

egy egészegyütthatós polinom. Tegyük fel tehát, hogy az ilyen alakú

F_{0}

F_{1}

...

F_{k}

polinomok

I

-nek egy generátorrendszerét alkotják. Ez azt jelenti, hogy e polinomok lineáris kombinációjaként az eredeti generátorrendszer minden eleme előállítható. Az

F_{0}

F_{1}

...

F_{k}

polinomrendszert lépésről lépésre meg fogjuk változtatni úgy, hogy az elemszám változatlanul marad, és rendre felhasználjuk, hogy ebből elő tudjuk állítani az eredeti generátorrendszer elemeit.
Tekintsük először az

U_{0} F_{0} + ... U_{k} F_{k} = 2^{n}

előállítást. Ha a fellépő polinomok konstans tagját a megfelelő kisbetűkkel jelöljük, akkor ebből ‐ a konstans tagok figyelembevételével ‐ az

u_{0} f_{0} + ... + u_{k} f_{k} = 2^{n}

egyenlőséghez jutunk. Tekintettel arra, hogy minden egyes

f_{i}

együttható osztható

2^{n}

-nel, ezért

2^{n}

ezeknek az együtthatóknak a legnagyobb közös osztója. A 6. Állítás szerint tehát vannak olyan

p_{0}

...

p_{k}

egész számok, hogy

G_{0} = p_{0} F_{0} + ... + p_{k} F_{k}

G_{1}

...

G_{k}

ismét generátorrendszer és

p_{0} f_{0} + ... + p_{k} f_{k} = 2^{n}

. Ez a szám viszont éppen a

G_{0}

konstans tagja, ami azt jelenti, hogy a kapott generátorrendszer egyik elemének a konstans tagja pontosan

2^{n}

. Ennek a polinomnak a megfelelő egész-számszorosát a generátorrendszer többi eleméből levonva a 4. Állítás alapján ismét generátorrendszert kapunk, és a kapott többi polinom konstans tagja 0 lesz.
A most kapott generátorrendszer elemeinek lineáris kombinációjaként előállítható a

2^{n - 1} x

polinom is. Mivel

G_{0}

konstans tagja nem 0, míg a többié 0, azért az előállításban az ehhez tartozó szorzó konstans tagja csak 0 lehet, mert különben a lineáris kombináció konstans tagja nem volna 0. Így a következő alakú előállításhoz jutunk:

\begin{matrix} x U_{0} G_{0} + U_{1} G_{1} + ... + U_{k} G_{k} = 2^{n - 1} x . \end{matrix}

x

-szel osztva és a konstans tagokra áttérve az

u_{0} g_{0} + ... + u_{k} g_{k} = 2^{n - 1}

egyenlőséghez jutunk, ahol a kisbetűk a megfelelő polinomok konstans tagját jelölik. Mivel mindegyik

g_{i}

osztható

2^{n - 1}

-gyel, azért a fenti egyenlőségből az következik, hogy

2^{n - 1}

g_{0}

g_{1}

...

g_{k}

számok legnagyobb közös osztója.
Igen lényeges észrevétel az, hogy

g_{0}

osztható

2^{n}

-nel is, és ezért már a

g_{1}

...

g_{k}

számok legnagyobb közös osztója is

2^{n - 1}

. Ismét a 7. Állítást használjuk fel. Eszerint a

G_{1}

...

G_{k}

polinomok helyettesíthetőek

H_{1} = p_{1} G_{1} + ... + p_{k} G_{k}

H_{2}

...

H_{k}

polinomokkal úgy, hogy

H_{1}

konstans tagja 0, elsőfokú tagjának együtthatója

2^{n - 1}

, és a többi polinomban a konstans is és az elsőfokú tag együtthatója is 0. Emellett a

G_{0}

változatlanul maradt. Mivel

G_{0}

I

-beli, azért

H_{1}

alkalmas egész-számszorosát levonva belőle egy olyan

H_{0}

polinomot nyerünk, amelyben az elsőfokú tag együtthatója 0. A 4. Állítás miatt ez ismét egy

H_{0}

H_{1}

...

H_{k}

generátorrendszert szolgáltat. Az eljárást folytatva végül egy olyan

M_{0}

M_{1}

...

M_{k}

generátorrendszert nyerünk, amelyben

M_{i} = 2^{n - i} m_{i} x^{i} + x^{k + 1} N_{i}

alakú. Ezeknek a lineáris kombinációjaként pedig csak úgy állítható elő az eredeti generátorrendszer, ha

k > n

A 2. Tétel bizonyítása. Legyen

I

Z [x]

-nek egy tetszőleges ideálja. Minden

n

természetes számhoz tekintsük az egész számoknak azt a

H_{n}

halmazát, amely az

I

-beli

n

-edfokú polinomok főegyütthatóit és még a 0-t tartalmazza. Mivel

I

ideál és

0 \in H_{n}

, azért

H_{n}

zárt az egész számokkal való lineáris kombináció képzésére. (Minden egyes

H_{n}

Z

-nek ideálja.) Tetszőleges

I

-beli

F

polinommal együtt

x F \in I

is igaz, és ezért

H_{n + 1} \supseteq H_{n}

.
Legyen

d_{n}

H_{n}

legkisebb pozitív eleme, ha ilyen létezik; és legyen

d_{n} = 0

egyébként. Ez utóbbi esetben persze

H_{n}

-ben nem is lehet más szám.
Tekintettel arra, hogy

H_{n}

zárt a lineáris kombináció képzésére, ezért bármely két

H_{n}

-beli elemmel együtt azok legnagyobb közös osztója is

H_{n}

-ben van. Ha

d_{n} \neq 0

, akkor ennek minden pozitív osztója nála kisebb; s mivel

d_{n}

H_{n}

-beli legkisebb pozitív egész szám, ezért

d_{n}

-nek és bármely

H_{n}

-beli számnak csak

d_{n}

lehet a legnagyobb közös osztója. Másszóval,

H_{n}

pontosan a

d_{n}

többszöröseiból áll. Mint láttuk

H_{n + 1} \supseteq H_{n}

; és így

d_{n}

is többszöröse

d_{n + 1}

-nek.
Lehetséges, hogy minden egyes

d_{n} = 0

. Ekkor persze

I

-ben nincs is 0-n kívül más polinom. Ebben az esetben 0 természetesen generátorrendszere

I

-nek. Egyébként van a

d_{n}

számok között pozitív; legyen egy ilyen a

d_{k}

. A pozitív számok oszthatósági tulajdonságainak alapján ekkor

d_{k} \geq d_{k + 1} \geq ...

teljesül. Mivel pozitív egész számok csökkenő sorozata csak véges lehet, azért van olyan természetes szám, hogy minden

i

természetes szám esetén már

d_{m + 1} = d_{m}

.
A

H_{n}

halmazok megadása szerint minden

n

-hez van olyan

F_{n}

polinom, amelynek a főegyütthatója pontosan

d_{n}

. Megmutatjuk, hogy az

F_{0}

F_{1}

...

F_{m}

polinomok

I

-nek egy generátorrendszerét alkotják. Tekintsük a

J = (F_{0}, F_{1}, ..., F_{n})

ideált. Legyen

F

tetszőleges

I

-beli polinom. Az

f

fokára vonatkozó teljes indukcióval bizonyítjuk, hogy

F \in I

.
Ha

F

konstans, akkor

H_{0}

definiciója szerint

F

egész-számszorosa

d_{0}

-nak, azaz valóban

F \in J

. Tegyük fel, hogy az állítás igaz minden olyan polinomra, amelynek a foka kisebb mint

n

, és legyen

F = a_{n} x^{n} + ...

egy

n

-edfokú polinom. A

H_{n}

definicója szerint

a_{n}

többszöröse

d_{n}

-nek:

a_{n} = b d_{n}

. Ha

n \leq m

, akkor tekintsük a

G = F - b F_{n}

polinomot, ha

n > m

, akkor meg a

G = F - b x^{n - m} F_{m}

polinomot. Az ideál-tulajdonság következtében

G \in I

; és mindkét esetben

G

-nek a foka kisebb, mint

F

-é. Az indukciós feltétel szerint tehát

G \in J

; s az ideáltulajdonság alapján

F \in J

is igaz.

Ez a gondolat átvihető annak a bizonyítására, hogy a 2. Tétel igaz véges sok határozatlanú polinomokra is. Igaz, a bizonyítás lényegesen hosszadalmasabb. Fogalmazzunk egy kicsit általánosabban.
Számok vagy polinomok egy (nem üres) halmazát gyűrűnek nevezzük, ha zárt az összeadásra, kivonásra és szorzásra. Tetszőleges gyűrűben hasonlóan definiálhatók az ideálok, mint ahogy fentebb tettük. Az algebrai geometriában alapvető fontosságúak azok a gyűrűk, amelyekben minden ideál véges sok elemmel generálható. Az ilyen gyűrűk neve Nöther gyűrű¹. Az az alapvető tulajdonság, amit a 2. Tétel bizonyításánál használtunk általában a következőképpen fogalmazható:

3. Tétel. Egy

S

gyűrű ideáljai pontosan akkor generálhatók véges sok elemmel, ha ideáljainak minden

I_{1} \subseteq I_{2} \subseteq ...

sorozatában valahonnét kezdve mindegyik ideál megegyezik.

Bizonyítás. Tegyük fel először, hogy

S

minden ideálja véges sok elemmel generálható, és tekintsünk egy

I_{1} \subseteq I_{2} \subseteq ...

ideálsorozatot. Legyen

I

ezeknek az ideáloknak az egyesítési halmaza. Tekintsük e halmaz

a

és

b

elemeit; illetve ezek egy

c = u a + v b

leneáris kombinációját.

I

definiciója alapján vannak olyan

i

j

indexek, hogy

a \in I_{i}

és

b \in I_{j}

. Feltehető, hogy

i \leq j

, amikor is

a

b \in I_{j}

, tehát

c \in I_{j}

; és így

c \in I

. Így

I

ideál. Eszerint generálható véges sok elemmel; legyenek ezek

u_{1}

...

u_{r}

. Mivel

I

az adott ideálok egyesítési halmaza, ezért vannak olyan indexek, hogy

u_{t} \in I_{i_{t}}

. Ha

n

a fenti indexek maximuma, akkor

u_{1}

...

u_{r} \in I_{n}

; így

I \subseteq I_{n}

, tehát minden

i

-re

I_{n + i} = I_{n}

.
Tegyük most fel azt, hogy minden

I - 1 \subseteq I_{2} \subseteq ...

ideálsorozat valahonnét kezdve ugyanabból az ideálból áll. Legyen

I

S

egy ideálja, és vegyük

I

-beli elemek egy

v_{1}

...

v_{s}

...

sorozatát a következó'képpen:

v_{1}

legyen tetszőleges. Ha már a

v_{1}

...

v_{i}

elemeket kiválasztottuk, akkor tekintsük az

I_{i} = (v_{1}, ..., v_{i})

ideált. Ha van az

I

-ben olyan elem, amelyik nincs az

I_{i}

-ben akkor ezek valamelyikét válasszuk

v_{i + 1}

-nek. Így egy növekvő ideálsorozatot kapunk, amelynek feltétel szerint vége szakad. Ez csak azért történhet meg, mert valamilyen

n

index esetén már

I_{n}

tartalmazza

I

minden elemét. Ez viszont pontosan azt jelenti, hogy

I = (v_{1}, ..., v_{i})

Fried Ervin

^*Megoldását ld. a cikket követően a a 481. oldalon.

¹A század első felében élt Emmy Nöther matematikus tiszteletére.