Ugrás a tartalomhoz

Új matematikai mozaik

Ambrus Gergely, Bárszi Gergely, Csikós Balázs, Frenkel Péter, Gács András, Gyárfás András, Hraskó András, Kiss Emil, Laczkovich Miklós, Lovász László, Montágh Balázs, Moussong Gábor, Pach János, Pelikán József, Recski András, Reiman István

Typotex

A körosztási polinomokról

A körosztási polinomokról

Laczkovich, Miklós


1. Számok és polinomok faktorizációja

A számelmélet egyik alapproblémája a számok faktorizációja, azaz prímtényezők szorzatára való felbontása. Ez a feladat általában nagyon nehéz, még speciális alakú számok esetében is. Tegyük fel, hogy faktorizálni szeretnénk azt a 16 jegyű k számot, amelynek első és utolsó jegye 1, a többi jegye pedig 0. Észrevehetjük, hogy k osztható 11-gyel, de az osztás után kapott szám, 90909090909091 faktorizációja nem látszik egyszerűnek. Közelebb jutunk a megoldáshoz, ha abból indulunk ki, hogy k = 10 15 + 1 , és először az x 15 + 1 polinomot faktorizáljuk:

x 15 + 1 = ( x 5 + 1 ) ( x 10 - x 5 + 1 ) = = ( x + 1 ) ( x 4 - x 3 + x 2 - x + 1 ) ( x 2 - x + 1 ) · · ( x 8 + x 7 - x 5 - x 4 - x 3 + x + 1 ) ,

amiből k = 11 · 9091 · 91 · 109889011 . Ez még nem a teljes faktorizáció, mert 91 = 7 · 13 , és 109889011 is összetett, de az eredeti feladatot mindenesetre visszavezettük egy 9-jegyű szám faktorizációjának problémájára. Ez lényegesen egyszerűbb, mint az eredeti feladat, és megoldhatjuk pl. úgy, hogy a vizsgált számot végigosztjuk a 10500-nál kisebb prímekkel. Azt kapjuk, hogy 109889011 = 211 · 241 · 2161 , tehát a keresett faktorizáció

k = 7 · 11 · 13 · 211 · 241 · 2161 · 9091 .

Az x n + 1 és x n - 1 polinomok faktorizációja nagyon sok számelméleti problémánál felbukkan. Az alábbiakban az x n - 1 polinomok faktorizációját fogjuk tárgyalni (ebből x n + 1 faktorizációja már megkapható; lásd az 1. feladatot), és egy fontos számelméleti alkalmazást is bemutatunk. Az x n - 1 polinomok felbontása az első néhány n -re a következő:

x - 1 = x - 1 x 2 - 1 = ( x - 1 ) ( x + 1 ) x 3 - 1 = ( x - 1 ) ( x 2 + x + 1 ) x 4 - 1 = ( x - 1 ) ( x + 1 ) ( x 2 + 1 ) x 5 - 1 = ( x - 1 ) ( x 4 + x 3 + x 2 + x + 1 ) x 6 - 1 = ( x - 1 ) ( x + 1 ) ( x 2 + x + 1 ) ( x 2 - x + 1 ) x 7 - 1 = ( x - 1 ) ( x 6 + x 5 + x 4 + x 3 + x 2 + x + 1 ) x 8 - 1 = ( x - 1 ) ( x + 1 ) ( x 2 + 1 ) ( x 4 + 1 ) x 9 - 1 = ( x - 1 ) ( x 2 + x + 1 ) ( x 6 + x 3 + 1 ) x 10 - 1 = ( x - 1 ) ( x + 1 ) ( x 4 + x 3 + x 2 + x + 1 ) ( x 4 - x 3 + x 2 - x + 1 ) x 11 - 1 = ( x - 1 ) ( x 10 + x 9 + x 8 + x 7 + x 6 + x 5 + x 4 + x 3 + x 2 + x + 1 ) x 12 - 1 = ( x - 1 ) ( x + 1 ) ( x 2 + x + 1 ) ( x 2 - x + 1 ) ( x 2 + 1 ) ( x 4 - x 2 + 1 ) x 13 - 1 = ( x - 1 ) · ( x 12 + x 11 + x 10 + x 9 + x 8 + x 7 + x 6 + x 5 + x 4 + x 3 + x 2 + x + 1 ) x 14 - 1 = ( x - 1 ) ( x + 1 ) ( x 6 + x 5 + x 4 + x 3 + x 2 + x + 1 ) · ( x 6 - x 5 + x 4 - x 3 + x 2 - x + 1 ) x 15 - 1 = ( x - 1 ) ( x 2 + x + 1 ) · ( x 4 + x 3 + x 2 + x + 1 ) ( x 8 - x 7 + x 5 - x 4 + x 3 - x + 1 ) x 16 - 1 = ( x - 1 ) ( x + 1 ) ( x 2 + 1 ) ( x 4 + 1 ) ( x 8 + 1 ) .

Az általános tétel kimondásához bevezetünk néhány fogalmat. Jelöljük Q [ x ] -szel a racionális együtthatós polinomok halmazát. Azt mondjuk, hogy a p ? Q [ x ] polinom osztója a q ? Q [ x ] polinomnak (és ezt úgy jelöljük, hogy p | q ), ha van olyan r ? Q [ x ] , amelyre q = p r . A p és q polinomok relatív prímek, ha nincs nem-konstans közös osztójuk. Egy polinomot főpolinomnak nevezünk, ha a főegyütthatója 1, azaz, ha x n + a n - 1 x n - 1 + + a 1 x + a 0 alakú.

Tétel. Léteznek páronként relatív prím egész együtthatós főpolinomok: F 1 , F 2 , úgy, hogy minden n ? 1 -re

x n - 1 = ? d | n F d ( x ) .

(1)

Jegyezzük meg, hogy az F d polinomok egyértelműen meg vannak határozva. Ugyanis szükségképpen F 1 ( x ) = x - 1 , és ha F k adott minden k //<// n -re, akkor

F n ( x ) = x n - 1 ? d | n d //<// n F d ( x ) .

Az F n polinomokat körosztási polinomoknak nevezzük. Ha n ? 16 , akkor F n -et megtaláljuk a fenti táblázatban, mint x n - 1 megadott felbontásának utolsó tényezője.

A tétel bizonyításához szükségünk lesz néhány további fogalomra és tételre. Egy p ? Q [ x ] polinomot irreducibilisnek nevezünk, ha legalább elsőfokú, és nem bontható fel alacsonyabb fokú racionális együtthatós polinomok szorzatára. (Pontosabban azt kellene mondani, hogy a polinom Q fölött irreducibilis, hangsúlyozva ezzel, hogy csak a racionális együtthatós polinomok szorzatára való felbontást zárjuk ki. Így pl. az x 2 - 2 polinom irreducibilis Q fölött, pedig alacsonyabb fokú valós együtthatós polinomokra felbontható: x 2 - 2 = ( x - 2 ) ( x + 2 ) . Tekintve, hogy a továbbiakban kizárólag racionális együtthatós polinomokkal foglalkozunk, ezért a „ Q fölött” kitételt elhagyjuk. Jegyezzük még meg, hogy minden elsőfokú racionális együtthatós polinom irreducibilis.) A racionális együtthatós polinomok számelméletében az irreducibilis polinomok a prímeknek felelnek meg.[21] A számelmélet alaptétele szerint minden 1-nél nagyobb egész felbontható prímek szorzatára, és ez az előállítás a tényezők sorrendjétől eltekintve egyértelmű. Ennek a polinomok körében a következő állítás felel meg: minden legalább elsőfokú racionális együtthatós polinom előáll racionális együtthatós irreducibilis polinomok szorzataként, és az előállítás egyértelmű, eltekintve a sorrendtől és konstans szorzóktól.

Mindkét állítást bebizonyítjuk. Először a számelmélet alaptételét, majd a bizonyítás kis módosításával a polinomok felbontására vonatkozó tételt látjuk be. A számelmélet alaptételét teljes indukcióval bizonyítjuk. Az állítás n = 2 -re nyilván igaz. Legyen n //>// 2 , és tegyük fel, hogy az n -nél kisebb számokra igaz a tétel. Ha n prím, akkor persze előáll mint prímek (egytényezős) szorzata. Ha n nem prím, akkor n = a b , ahol 1 //<// a , b //<// n , így a és b is előáll mint prímek szorzata, tehát ugyanez n -re is igaz. Az egyértelműséget bizonyítandó legyen n = p 1 p 2 p k = q 1 q 2 q m két előállítás. Feltehető, hogy p 1 , p 2 , , p k , q 1 , q 2 , , q m közül q 1 az (egyik) legkisebb. Elég belátni, hogy q 1 szerepel a p i -k között, hiszen ha q 1 = p i , akkor n / q 1 = p 1 p i - 1 p i + 1 p k = q 2 q m , és az indukciós feltevés alapján készen vagyunk.

Tegyük fel, hogy nem ez a helyzet, azaz q 1 ? p i ( i = 1 , , k ) . Legyen n ' = ( p 1 - q 1 ) p 2 p k = n - q 1 p 2 p k . Ekkor 0 //<// n ' //<// n . Mivel n osztható q 1 -gyel, így n ' is. Ebből következik, hogy n ' -nek van olyan prímtényezős felbontása, amelyben q 1 szerepel: vegyük n ' / q 1 prímtényezős felbontását és szorozzuk meg q 1 -gyel. De n ' -nek olyan prímtényezős felbontása is van, amelyben q 1 nem szerepel: vegyük p 1 - q 1 prímtényezős felbontását és szorozzuk meg p 2 p k -val. Itt p 1 - q 1 prímtényezős felbontásában q 1 nem szerepelhet, mert p 1 egy q 1 -től különböző prím, tehát p 1 és p 1 - q 1 nem oszthatók q 1 -gyel, továbbá az indirekt feltevésünk szerint p 2 , , p k mindegyike különbözik q 1 -től. Azt kaptuk, hogy n ' -nek van két különböző prímtényezős felbontása, ami ellentmond az indukciós feltevésnek. Ezzel a számelmélet alaptételének bizonyítását befejeztük.

Most rátérünk a polinomokra vonatkozó állítás bizonyítására. A polinomok fokszáma szerinti indukciót alkalmazunk. Ha az r ? Q [ x ] polinom elsőfokú, akkor irreducibilis, tehát előáll mint irreducibilis polinomok (egytényezős) szorzata, és az előállítás nyilván egyértelmű. Legyen r foka n //>// 1 , és tegyük fel, hogy az n -nél kisebb fokú polinomokra igaz a tétel. Ha r irreducibilis, akkor az állítás r -re is igaz. Ha nem, akkor r = p q , ahol p és q alacsonyabb fokú racionális együtthatós polinomok. Így p és q is előáll mint irreducibilisek szorzata, tehát ugyanez r -re is igaz. Az egyértelműséget bizonyítandó legyen r = p 1 p 2 p k = q 1 q 2 q m két előállítás. Feltehető, hogy p 1 , p 2 , , p k , q 1 , q 2 , , q m közül q 1 az (egyik) legalacsonyabb fokú. Elég belátni, hogy q 1 (vagy egy racionális konstansszorosa) szerepel a p i -k között, hiszen ha c · q 1 = p i , akkor r / q 1 = c p 1 p i - 1 p i + 1 p k = q 2 q m , és az indukciós feltevés alapján készen vagyunk.

Tegyük fel, hogy nem ez a helyzet. Legyen p 1 és q 1 fokszámainak különbsége d , a főegyütthatóinak hányadosa pedig a ; ekkor p 1 - a · x d q 1 foka alacsonyabb p 1 fokánál. Ebből következik, hogy az r ' = ( p 1 - a · x d q 1 ) p 2 p k = r - a · x d · q 1 p 2 p k polinom alacsonyabb fokú, mint r , de nem konstans. Innen pontosan ugyanúgy jutunk ellentmondásra, mint a számelmélet alaptételének bizonyításában.

Még egy segédtételre lesz szükségünk. Belátjuk, hogy ha p és q egész együtthatós polinomok , q főpolinom és q | p , akkor p / q is egész együtthatós. Ezt p foka szerinti indukcióval bizonyítjuk. Ha p azonosan 0, akkor az állítás igaz. Tegyük fel, hogy p legalább 0-adfokú (vagyis nem azonosan 0), és hogy az állítás igaz minden alacsonyabb fokú polinomra. Legyen p főegyütthatója c , és legyen p 1 = p - c · x k q , ahol k egyenlő p és q fokszámainak különbségével. Ekkor p 1 alacsonyabb fokú, mint p , egész együtthatós és osztható q -val. Az indukciós feltevés szerint p 1 / q = ( p / q ) - c · x k egész együtthatós, és így ugyanez igaz p / q = ( p 1 / q ) + c · x k -ra is, hiszen c egész szám. Ezzel az állítást beláttuk.

A fentiekből nyilvánvalóan következik, hogy ha p és q egész együtthatós főpolinomok és q | p , akkor p / q is egész együtthatós főpolinom.

Most rátérünk a tétel bizonyítására. Legyen F 1 ( x ) = x - 1 . Tegyük fel, hogy N //>// 1 , és hogy az F 1 , , F N - 1 páronként relatív prím egész együtthatós főpolinomokat már definiáltuk úgy, hogy (1) teljesül minden n //<// N -re. Ha d | N és d //<// N , akkor F d | x d - 1 | x N - 1 . Mivel F 1 , , F N - 1 páronként relatív prímek, ezért a q = ? d | N d //<// N F d ( x ) egész együtthatós főpolinom osztója x N - 1 -nek (itt felhasználtuk az irreducibilis faktorokra való felbontás egyértelműségét). Legyen F N ( x ) = ( x N - 1 ) / q , ekkor tehát F N is egész együtthatós főpolinom, és (1) teljesül n = N -re.

A bizonyítás befejezéséhez azt kell még megmutatni, hogy F N és F n relatív prímek minden n //<// N -re. Tegyük fel, hogy ez nem igaz, és legyen p egy közös irreducibilis osztója F N -nek és F n -nek valamely n //<// N -re. Mivel F n | x n - 1 és F N | x N - 1 , így

p | x N - 1 - x N - n ( x n - 1 ) = x N - n - 1 = ? d | N - n F d .

Mármost p irreducibilitásából következik (ismét az egyértelmű felbontás alapján), hogy p osztója F d -nek valamely d | N - n -re. Így p közös osztója F n -nek és F d -nek, ami csak úgy lehetséges, ha n = d (hiszen egyébként F n és F d relatív prímek lennének), azaz n | N . Ekkor viszont

p | F N = x N - 1 ? d | N d //<// N F d x N - 1 x n - 1 = 1 + x n + x 2 n + + x N - n = = ( x n - 1 ) + ( x 2 n - 1 ) + + ( x N - n - 1 ) + N n .

Az utóbbi összegben az utolsó kivételével minden tag osztható x n - 1 -gyel, tehát F n -nel, tehát p -vel is. Ezért p osztója az N / n konstans polinomnak, ami lehetetlen. Ezzel megmutattuk, hogy F N valóban relatív prím az összes, kisebb indexű F n polinomhoz, amivel a kívánt polinomsorozat létezését beláttuk.



[21] Az előzőekben és a továbbiakban is prímszámon felbonthatatlan számot értünk: egy pozitív egész számot akkor nevezünk prímnek, ha nagyobb 1-nél, és nem bontható fel két kisebb pozitív egész szám szorzatára.