Feladat: N.55 Korcsoport: 18- Nehézségi fok: nehéz
Megoldó(k):  Braun Gábor ,  Dombi Gergely ,  Gyarmati Katalin ,  Póczos Barnabás ,  Valkó Benedek 
Füzet: 1995/szeptember, 353 - 354. oldal  PDF file
Témakör(ök): Polinomok, Maradékos osztás, kongruenciák, Nehéz feladat
Hivatkozás(ok):Feladatok: 1995/január: N.55

Van-e olyan egész együtthatós polinom, amelynek nincs egész gyöke, de tetszőleges pozitív egész n mellett van gyöke modulo n?

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.

Bebizonyítjuk, hogy a P(x)=(x3+3)(x2+1)(x2+2)(x2-2) polinom, amelynek főegyütthatója 1, kielégíti a feladat feltételeit. Látható, hogy nincs egész gyöke, így elég bebizonyítani, hogy minden n-re van gyöke mod n.
Használni fogjuk az ún. Legendre-féle szimbólumot: ha p 2-nél nagyobb prím és a egész, akkor

(ap)={0,ha  pa
 
1,ha  pa  és az  x2a  (mod  p) megoldható
 
-1,ha az  x2a  (mod  p) nem oldható meg.
Ismert, hogy (ap)ap-12 (mod p) (a bizonyítás megtalálható Szalay Mihály: Számelmélet c. spec. mat. tankönyvének 95‐96. oldalán, Tankönyvkiadó, 1991). Így
(-1p)(2p)(-2p)=(-1)p-122p-12(-2)p-12=(-2)p-11(modp)
minden páratlan p prímre. Tehát (-1p), (2p), (-2p) közül valamelyik +1, azaz az x2-1, x22, x2-2 valamelyike megoldható mod p.
Belátjuk, hogy ha x2a (mod p) megoldható (p páratlan prím, pa), akkor x2a (mod pk) is megoldható minden k1-re. Teljes indukcióval bizonyítunk.
k=1-re az állítás igaz. Tegyük fel, hogy valamilyen k1 egészre x2a (mod p) megoldható, legyen egy megoldása xx1 (mod pk). Ekkor
(pkl+x1)2=p2kl2+2pklx1+x12(2lx1)pk+x12(modpk+1),
azaz
(pkl+x1)2-a(2lx1)pk+x12-a=(2lx1)pk+bpk(modpk+1)
valamely b egészre. p2x1 miatt van olyan l egész, amelyre p2lx1+b, így valamilyen y=pkl=x1 számra y2-a0 (mod pk+1), tehát y2a (mod pk+1). Ezt akartuk bizonyítani.
Ezzel beláttuk, hogy minden páratlan p prímre és k1 egészre az x2-1,
x22, x2-2 valamelyike megoldható mod pk. Ekkor nyilván a p(x) polinomnak is van gyöke modulo pk.
Vizsgáljuk most a p=2 esetet. Bebizonyítjuk, hogy az x3+30-nak van gyöke mod 2k, minden k1-re.
Teljes indukcióval bizonyítunk. k=1 esetén x1 (mod 2) megoldás. Tegyük fel, hogy x3+30 (mod 2k) megoldható, legyen egy megoldás x1. Keressük a modulo 2k+1 megoldást y=2kl+x1 alakban.
(2kl+x1)323k+322kl2x1+32klx12+x1332klx1+x13,
azaz
(2kl+x1)3+3(3lx12)2k+x13+3=(3lx12)2k+b2k(mod  2k+1),
valamilyen b egészre. Az x1 biztosan páratlan (mert 2kx13+3), így valamilyen l-re 23lx12+b, és ekkor y=2kl+x1-re y2+30 (mod 2k+1).
Ezzel bebizonyítottuk, hogy tetszőleges pk prímhatványra a P(x) polinomnak van gyöke modulo pk.
Legyen az n prímtényezős felbontása p1α1p2α2...prαr. Tudjuk, hogy van a polinomnak xi gyöke modulo piαi minden 1ir-re.
A kínai maradéktétel alapján az
xx1modp1α1,xx2modp2α2,...,xxrmodprαr
kongruencia-rendszernek van egy x megoldása. Erre az x-re P(x) osztható lesz piαi-vel minden 1ir-re, tehát osztható lesz n-nel is.
Ezzel a feladat állítását bebizonyítottuk.
 
Megjegyzés. A feladat szövegéből kimaradt az a feltétel, hogy a polinom főegyütthatója legyen 1. Ennek a feltételnek a hiányában könnyebb olyan polinomot mutatni, amely kielégíti a feladat feltételeit (és főegyütthatója nem 1). Pl. a (2x+1)(3x+1) polinomnak nincs egész gyöke, és ‐ ugyancsak a kínai maradéktétel segítségével ‐ egyszerűen belátható, hogy van gyöke modulo n, minden n>1 természetes számra.