Kezdőlap


Cím:	A kínai maradéktétel polinomokra
Szerző(k):	Kós Géza
Füzet:	1986/március, 97 - 101. oldal	PDF \| MathML
Témakör(ök):	Szakmai cikkek

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.

(Megjegyzés a 2508. feladathoz)^{$^{*}$}

A 2508. feladatban olyan ötödfokú

f

polinomot kellett megadni, amelyre teljesül, hogy

[f (x) - 1]

-ből

{(x + 1)}^{3}

[f (x) + 1]

-ből pedig

{(x - 1)}^{3}

kiemelhető. Azt, hogy ilyen polinom létezik, a feladat feltételezte.
De vajon akkor is létezik-e megoldás, ha a konstansokat megváltoztatjuk, azaz: megadható-e olyan

n

-edfokú

f

polinom, amelyre teljesül, hogy

[f (x) - α_{i}]

-ből

(x - β_{i})^{γ_{i}}

kiemelhető, ahol

α_{1}

α_{2}

...

α_{k}

β_{1}

β_{2}

...

β_{k}

adott valós számok,

γ_{1}

γ_{2}

...

γ_{k}

adott pozitív egészek?
Ez a kérdés emlékeztet egy számelméleti problémára:
Legyenek

m_{1}

m_{2}

...

m_{k}

;

a_{1}

a_{2}

...

a_{k}

egész számok. Létezik-e olyan

M

egész szám, amelyre teljesül, hogy

M - a_{i}

osztható

m_{i}

-vel?
A probléma így egy bizonyára sokak által ismert feladattípus általános megfogalmazása. Például a következő formában találkozhattunk vele: ha néhány gyereket párosával állítunk sorba, akkor egy gyerek marad a sor végén, ha hármasával, akkor pedig kettő. Hányan maradnak, ha hatosával állítjuk őket sorba?
A kérdés megválaszolásához olyan

M

számokat kell keresnünk, amelyek

2

-vel osztva

1

3

-mal osztva pedig

2

maradékot adnak, azaz

M - 1

osztható

2

-vel,

M - 2

pedig osztható

3

-mal. Egyszerűen belátható, hogy éppen a

6

-tal osztva

5

maradékot adó számok rendelkeznek a fenti tulajdonsággal.
Ami az általános számelméleti problémát illeti, a szóban forgó

M

szám nem feltétlenül létezik. Legyen például

m_{1} = 4

m_{2} = 6

a_{1} = 1

és a

a_{2} = 2

. Ha most

M - 1

osztható

4

-gyel, akkor

M

páratlan és így

M - 2

nem lehet

6

-tal osztható. Ebben a példában

m_{1}

és

m_{2}

is páros volt, és hasonló ellenpéldák készíthetők általában is, ha az adott

m_{i}

-k között vannak páronként nem relatív prímek. A 2508. feladatban szereplő

m_{1} (x) = {(x + 1)}^{3}

és

m_{2} (x) = {(x - 1)}^{3}

polinomok azonban számelméleti szempontból nem ilyenek. Nincs közös tényezőjük, a legnagyobb közös osztójuk

1

. Nos, ha az adott

m_{i}

számok páronként relatív prímek, akkor már igennel válaszolhatunk a feltett kérdésre, ahogy ezt az alábbi tétel állítja:

(I) Kínai maradéktétel
Ha

m_{1}

m_{2}

...

m_{k}

páronként relatív prím egész számok és

a_{1}

a_{2}

...

a_{k}

tetszőleges egész számok, akkor az

M \equiv a_{i} (mod m_{i})

kongruenciáknak van közös

M

megoldása, és a megoldások kongruensek modulo

m_{1} \cdot m_{2} \cdot ... \cdot m_{k}

.
A tételt megfogalmazhatjuk a polinomok nyelvén is:

(II) Ha az

m_{1}

m_{2}

...

m_{k}

polinomok páronként relatív prímek (azaz nem emelhető ki belőlük ugyanaz a legalább elsőfokú polinom),

a_{1}

a_{2}

...

a_{k}

pedig tetszőleges polinomok, akkor van olyan

M

polinom, amelyre teljesül, hogy

[M (x) - a_{i} (x)]

-ből

m_{i} (x)

kiemelhető; bármely két ilyen

M

polinom különbségéből

m_{1} (x) \cdot m_{2} (x) \cdot ... \cdot m_{k} (x)

kiemelhető.
Ez az átfogalmazás annyira szerencsés, hogy még a bizonyítása is szinte szóról szóra megegyezik (I) bizonyításával.

(III) A maradéktétel bizonyítása
a) Mivel

m_{1}

m_{2}

...

m_{k}

páronként relatív prímek,

m_{i}

és

m_{1} \cdot m_{2} \cdot ... \cdot m_{i - 1} \cdot m_{i + 1} \cdot ... \cdot m_{k} = \frac{m_{1} \cdot m_{2} ... \cdot m_{k}}{m_{i}}

is relatív prímek. Ekkor viszont létezik olyan

b_{i}

egész szám, amelyre

b_{i} \cdot \frac{m_{1} m_{2} ... m_{k}}{m_{i}} \equiv 1 (mod m_{i})

. Ekkor pedig

\begin{matrix} M = \sum_{j = 1}^{k} a_{j} b_{j} \cdot \frac{m_{1} m_{2} ... m_{k}}{m_{j}} \end{matrix}

megoldás, hiszen

j \neq i

esetén

a_{j} b_{j} \cdot \frac{m_{1} m_{2} ... m_{k}}{m_{j}}

osztható

m_{i}

-vel és így

\begin{matrix} M = \sum_{j = 1}^{k} a_{j} b_{j} \cdot \frac{m_{1} m_{2} ... m_{k}}{m_{j}} \equiv a_{i} b_{i} \cdot \frac{m_{1} m_{2} ... m_{k}}{m_{i}} \equiv a_{i} \cdot 1 = a_{i} (mod m_{i}) \end{matrix}

minden

1 ≦ i ≦ k

-ra.

b) Ha

M_{1}

és

M_{2}

két megoldás, akkor

M_{1} - M_{2}

osztható

m_{1}

m_{2}

...

m_{k}

mindegyikével, így

[m_{1}, m_{2}, ..., m_{k}] = m_{1} m_{2} ... m_{k}

-val is, tehát

\begin{matrix} M_{1} \equiv M_{2} (mod m_{1} m_{2} ... m_{k}) . \end{matrix}

Megfordítva, ha

M_{1}

megoldás és

M_{2} \equiv M_{1} (mod m_{1} m_{2} ... m_{k})

, akkor

M_{2}

is megoldás. A megoldások tehát egy modulo

m_{1} m_{2} ... m_{k}

maradékosztály elemei.
(A kínai maradéktétel legalább 2000 éves ‐ természetesen nem ebben az általános formában. Történetéről Davis‐Hersh: A matematika élménye c. műben olvashatunk, Műszaki Könyvkiadó, 1984. Az utóbbi időben a tételt nagy számokkal végzett számításokra kidolgozott algoritmusokban alkalmazták eredményesen. Erről bővebben: Lovász‐Gács: Algoritmusok, Műszaki Könyvkiadó, 1978 c. mű ,,Moduláris algoritmusok'' c. fejezetében olvashatunk. A szerk.)

Ahhoz, hogy ugyanezt a bizonyítást elmondhassuk (II)-re is, csupán egy felhasznált tételt kell bebizonyítanunk.

(IV) Ha

p

és

q

relatív prím polinomok, akkor van olyan

r

polinom, hogy

r (x) \cdot p (x) \equiv 1 (mod q (x))

, azaz vannak olyan

r

és

s

polinomok, amelyekre teljesül, hogy

r (x) \cdot p (x) - s (x) \cdot q (x) = 1

.
A bizonyításhoz az euklideszi algoritmus módszerét alkalmazzuk. Legyen

p

fokszáma

α

q

-é

β

. Ha

α ≧ β

, akkor legyen

\begin{matrix} P (x) = p (x) - h \cdot x^{α - β} \cdot q (x) és Q (x) = q (x), \end{matrix}

ellenkező esetben

\begin{matrix} P (x) = p (x) és Q (x) = q (x) - \frac{1}{h} \cdot x^{β - α} \cdot p (x), \end{matrix}

ahol

h

p

és

q

polinomok főegyütthatóinak hányadosa.

P

vagy

Q

fokszáma ezzel kisebb lett, mint

p

, illetve

q

fokszáma, másfelől

P

és

Q

továbbra is relatív prímek, hiszen ha egy nem konstans

f (x)

polinom kiemelhető lenne belőlük, akkor ugyanez kiemelhető lenne

\begin{matrix} p (x) = P (x) + h x^{α - β} Q (x) és q (x) = Q (x) -ből, illetve \\ p (x) = P (x) és q (x) = Q (x) + \frac{1}{h} x^{β - α} P (x) -ből is . \end{matrix}

A fenti fokszámcsökkentés éppen az euklideszi algoritmus maradékos osztásának első fázisa és (IV) bizonyításán túl az állításban szereplő

r (x)

és

s (x)

polinomok kiszámolására is alkalmas algoritmus egy lépése.
Lássuk tehát a bizonyítást a

p

és a

q

fokszámának összege szerinti teljes indukcióval!
Ha

p

és

q

fokszámának összege

0

, akkor mindkét polinom konstans, és

r (x) = \frac{1}{p}

és

s (x) = 0

megfelelő. Tegyük fel, hogy a bizonyítást elvégeztük azokra az esetekre, amikor a fokszámok összege kisebb, mint

n

.
Bebizonyítjuk az állítást akkor is, amikor ez az összeg éppen

n

. Definiáljuk a

P

és

Q

polinomokat az előbbiek szerint! Ezek relatív prímek, és fokszámaik összege kisebb, mint

p

és

q

fokszámának összege,

n

. Ezért az indukciós feltevés szerint léteznek olyan

R

és

S

polinomok, hogy

R (x) \cdot P (x) - S (x) \cdot Q (x) = 1

.
Most írjunk

P (x)

Q (x)

helyére

p (x) - h x^{α - β} q (x)

q (x)

-et, illetve

p (x)

q (x) - \frac{1}{h} x^{β - α} p (x)

-et:

\begin{matrix} R (x) \cdot [p (x) - h x^{α - β} q (x)] - S (x) q (x) = R (x) p (x) - [h x^{α - β} + S (x)] \cdot q (x) = 1, \end{matrix}

illetve

\begin{matrix} R (x) p (x) - S (x) \cdot [q (x) - \frac{1}{h} x^{β - α} p (x)] = \\ = [\frac{1}{h} x^{β - α} + R (x)] p (x) - S (x) q (x) = 1. \end{matrix}

Azt kaptuk tehát, hogy

r (x) = R (x)

és

s (x) = S (x) + h x^{α - β}

, illetve

r (x) = R (x) + \frac{1}{h} x^{β - α}

és

s (x) = S (x)

megfelelő.

Most már bebizonyíthatjuk a (II) állítást:

(V) a) Mivel az

m_{1}

m_{2}

...

m_{k}

polinomok közül semelyik kettőnek nincs közös (komplex) gyöke,

m_{i}

-nek és

m_{1} \cdot m_{2} \cdot ... \cdot m_{i - 1} \cdot m_{i + 1} \cdot ... \cdot m_{k} = \frac{m_{1} m_{2} ... m_{k}}{m_{i}}

-nek sincs, tehát

m_{i}

és

\frac{m_{1} m_{2} ... m_{k}}{m_{i}}

relatív prímek.
(IV) alapján tehát létezik olyan

b_{i}

polinom, hogy

[b_{i} (x) \frac{m_{1} (x) m_{2} (x) ... m_{k} (x)}{m_{i} (x)} - 1]

-ből

m_{i} (x)

kiemelhető.
Ebből pedig következik, hogy

\begin{matrix} M (x) = a_{1} (x) b_{1} (x) \frac{m_{1} (x) m_{2} (x) ... m_{k} (x)}{m_{1} (x)} + \\ + a_{2} (x) b_{2} (x) \frac{m_{1} (x) m_{2} (x) ... m_{k} (x)}{m_{2} (x)} + ... + a_{k} (x) b_{k} (x) \frac{m_{1} (x) m_{2} (x) ... m_{k} (x)}{m_{k} (x)} \end{matrix}

megoldás, hiszen minden

1 ≦ i ≦ k

-ra

\begin{matrix} M (x) - a_{i} (x) = a_{1} (x) b_{1} (x) \frac{m_{1} (x) ... m_{k} (x)}{m_{1} (x)} + ... + a_{i - 1} (x) b_{i - 1} (x) \frac{m_{1} (x) ... m_{k} (x)}{m_{i - 1} (x)} + \\ + a_{i} (x) [b_{i} (x) \frac{m_{1} (x) ... m_{k} (x)}{m_{i} (x)} - 1] + \\ + a_{i + 1} (x) b_{i + 1} (x) \frac{m_{1} (x) ... m_{k} (x)}{m_{i + 1} (x)} + ... + a_{k} (x) b_{k} (x) \frac{m_{1} (x) ... m_{k} (x)}{m_{k} (x)} \end{matrix}

minden tagjából kiemelhető

m_{i} (x)

.
b) Ha

M_{1}

és

M_{2}

két különböző megoldás, akkor

M_{1} - M_{2}

-ből

m_{1}

m_{2}

...

m_{k}

mindegyike kiemelhető. Ekkor viszont összes (komplex) gyöktényezőjük kiemelhető, így

m_{1} m_{2} ... m_{k}

is, ami ezek szorzatának egy konstansszorosa.
A megfordítás ugyanúgy bizonyítható, mint a kínai maradéktétel:
Ha

M_{1}

megoldás és

M_{1} - M_{2}

-ből

m_{1} m_{2} ... m_{k}

kiemelhető, akkor

M_{2}

is megoldás, mert minden

1 ≦ i ≦ k

-ra

\begin{matrix} M_{2} (x) - a_{i} (x) = [M_{1} (x) - a_{i} (x)] - [M_{1} (x) - M_{2} (x)] -ből \end{matrix}

m_{i} (x)

kiemelhető.
Ezzel (II)-t bebizonyítottuk.

A 2508. feladatban szereplő polinomok együtthatói egész számok voltak, így joggal vetődik fel a kérdés, vajon várható-e, hogy a kapott

M

polinom is ilyen. A kulcsfontosságú (IV) állítás bizonyításának indukciós lépésében a

P (x)

és a

Q (x)

együtthatóinak számolásakor a

p (x)

és a

q (x)

főegyütthatóinak

h

hányadosát használjuk, ami nem szükségképpen egész, így a végül kapott

r (x)

és

s (x)

polinomok együtthatóiról csak annyit állíthatunk, hogy racionálisak, és így a felhasználásukkal nyert

M

polinom is ilyen.
A (II) tételben ugyanakkor a komplex számtestbe ágyazva fogalmaztuk meg az

m_{i}

polinomok relatív prím voltát. Az oszthatóság ténye a polinomok között függ attól, hogy milyen számkörből valók az együtthatók. Az egész együtthatós polinomok körében például a

2 x + 2

polinom nem osztója a

3 x^{2} + 3 x

polinomnak, a racionális együtthatós polinomok körében már igen

[3 x^{2} + 3 x = \frac{3}{2} x (2 x + 2)]

.
(A legnagyobb közös osztó ‐ és így a polinomok relatív prím volta ‐ viszont nem függ attól, hogy az egész, a racionális, a valós vagy pedig a komplex számkörből indulunk-e ki. Az algebra alaptételének felhasználásával megmutatható, hogy ha két egész együtthatós polinomnak

1

a legnagyobb közös osztója, akkor nem lehet közös komplex gyökük sem; a feltételben tehát jogosan használtuk az ilyen polinomok relatív prím voltának e legáltalánosabb jellemzését. A szerk.)

(II) egyszerű következménye az alábbi tétel.
(VI) Legyenek

m_{1}

m_{2}

...

m_{k}

páronként relatív prím polinomok,

m_{i}

fokszáma

φ_{i}

;

a_{1}

a_{2}

...

a_{k}

pedig tetszőleges polinomok. Ekkor pontosan egy olyan

M

polinom létezik, amelynek fokszáma kisebb, mint

φ_{1} + φ_{2} + ... + φ_{k}

, és

[M - a_{i} (x)]

-ből

m_{i} (x)

kiemelhető

(i = 1,2, ..., k)

.
Ilyen megoldást előállíthatunk az ismert osztási algoritmus segítségével: egy tetszőleges

M^{*}

polinomot, amely eleget tesz az

M^{*} (x) = a_{i} (x) (mod m_{i} (x))

kongruenciáknak, elosztjuk az

m_{1} (x) \cdot m_{2} (x) \cdot ... \cdot m_{k} (x)

polinommal, és az osztási maradék megfelelő lesz.
Az is könnyen látható, hogy legfeljebb egy ilyen polinom létezik; ha

M_{1}

és

M_{2}

is eleget tenne a feltételeknek,

M_{1} - M_{2}

osztható lenne

m_{1} m_{2} ... m_{k}

-val. Mivel viszont

M_{1} - M_{2}

fokszáma kisebb, mint

m_{1} m_{2} ... m_{k}

fokszáma,

φ_{1} + φ_{2} + ... + φ_{k}

, azért

M_{1} - M_{2}

csak azonosan

0

lehet, ami ellentmond annak a feltételezésünknek, hogy

M_{1}

és

M_{2}

különböző.
Befejezésül nézzük meg a 2508. feladat egy némiképp számolásigényes megoldását a fenti eredmények felhasználásával. Az adatok:

\begin{matrix} m_{1} (x) = x^{3} + 3 x^{2} + 3 x + 1 & , m_{2} (x) = x^{3} - 3 x^{2} + 3 x - 1, \\ a_{1} (x) = 1 & , a_{2} (x) = - 1. \end{matrix}

Először írjuk fel azokat az

r (x)

és

s (x)

polinomokat, amelyekre a (IV) állítás szerint

r (x) \cdot m_{1} (x) - s (x) \cdot m_{2} (x) = 1

.
Az

m_{1} (x)

és

m_{2} (x)

polinomok között az euklideszi algoritmust elvégezve és a maradékokat kifejezve:

\begin{matrix} m_{1} (x) = m_{2} (x) + (6 x^{2} + 2), & ebből 6 x^{2} + 2 = m_{1} (x) - m_{2} (x), & (1) \\ m_{2} (x) = (\frac{1}{6} x - \frac{1}{2}) (6 x^{2} + 2) + \frac{8}{3} x, & ebből \frac{8}{3} x = m_{2} (x) - (6 x^{2} + 2) (\frac{1}{6} x - \frac{1}{2}), & (2) \\ 6 x^{2} + 2 = \frac{9}{4} x \cdot \frac{8}{3} x + 2, & ebből 2 = (6 x^{2} + 2) - \frac{8}{3} x \cdot \frac{9}{4} x . & (3) \end{matrix}

(2)-ből (1) alapján

\begin{matrix} \frac{8}{3} x = m_{2} (x) - [m_{1} (x) - m_{2} (x)] \cdot [\frac{1}{6} x - \frac{1}{2}] = & (4) \\ = m_{2} (x) \cdot [\frac{1}{6} x - \frac{1}{2}] - m_{1} (x) \cdot [\frac{1}{6} x - \frac{1}{2}], \end{matrix}

és (3)-ból hasonlóan kapjuk (4) és (l) felhasználásával, hogy

\begin{matrix} 2 = m_{1} (x) \cdot (\frac{3}{8} x^{2} - \frac{9}{8} x + 1) - m_{2} (x) \cdot (\frac{3}{8} x^{2} + \frac{9}{8} x + 1) \end{matrix}

Ha mindkét oldalt osztjuk 2-vel, akkor épp a kívánt felbontást kapjuk, innen tehát

\begin{matrix} r (x) = \frac{3}{16} x^{2} - \frac{9}{16} x + \frac{1}{2} és s (x) = \frac{3}{16} x^{2} - \frac{9}{16} x + \frac{1}{2} . \end{matrix}

A (II) tétel bizonyítása, (V) alapján most már felírhatjuk az

M

polinomot.

\begin{matrix} M (x) = 1 \cdot [- s (x)] \cdot \frac{m_{1} (x) m_{2} (x)}{m_{1} (x)} + (- 1) \cdot r (x) \cdot \frac{m_{1} (x) m_{2} (x)}{m_{2} (x)} = \\ = - s (x) \cdot m_{2} (x) - r (x) \cdot m_{1} (x) = - \frac{3}{8} x^{5} + \frac{5}{4} x^{3} - \frac{15}{8} x . \end{matrix}

^{$^{*}$}A 2508. feladat megoldása az 1985. évi 10. szám 442‐444.oldalán olvasható.