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  |  MathML 
Témakör(ök): Polinomok, Maradékos osztás, kongruenciák, Nehéz feladat
Hivatkozás(ok):Feladatok: 1995/január: N.55

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  p∣a
 
1,ha  p∤a  és az  x2≡a  (mod  p) megoldható
 
-1,ha az  x2≡a  (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-12⋅2p-12⋅(-2)p-12=(-2)p-1≡1(modp)
minden páratlan p prímre. Tehát (-1p), (2p), (-2p) közül valamelyik +1, azaz az x2≡-1, x2≡2, x2≡-2 valamelyike megoldható mod p.
Belátjuk, hogy ha x2≡a (mod p) megoldható (p páratlan prím, p∤a), akkor x2≡a (mod pk) is megoldható minden k≥1-re. Teljes indukcióval bizonyítunk.
k=1-re az állítás igaz. Tegyük fel, hogy valamilyen k≥1 egészre x2≡a (mod p) megoldható, legyen egy megoldása x≡x1 (mod pk). Ekkor
(pkl+x1)2=p2kl2+2pklx1+x12≡(2lx1)pk+x12(modpk+1),
azaz
(pk⋅l+x1)2-a≡(2lx1)pk+x12-a=(2lx1)pk+bpk(modpk+1)
valamely b egészre. p∤2x1 miatt van olyan l egész, amelyre p∣2lx1+b, így valamilyen y=pk⋅l=x1 számra y2-a≡0 (mod pk+1), tehát y2≡a (mod pk+1). Ezt akartuk bizonyítani.
Ezzel beláttuk, hogy minden páratlan p prímre és k≥1 egészre az x2≡-1,
x2≡2, 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+3≡0-nak van gyöke mod 2k, minden k≥1-re.
Teljes indukcióval bizonyítunk. k=1 esetén x≡1 (mod 2) megoldás. Tegyük fel, hogy x3+3≡0 (mod 2k) megoldható, legyen egy megoldás x1. Keressük a modulo 2k+1 megoldást y=2k⋅l+x1 alakban.
(2k⋅l+x1)3≡23k+3⋅22kl2x1+3⋅2klx12+x13≡3⋅2klx1+x13,
azaz
(2k⋅l+x1)3+3≡(3lx12)2k+x13+3=(3lx12)⋅2k+b⋅2k(mod  2k+1),
valamilyen b egészre. Az x1 biztosan páratlan (mert 2k∣x13+3), így valamilyen l-re 2∣3lx12+b, és ekkor y=2k⋅l+x1-re y2+3≡0 (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 1≤i≤r-re.
A kínai maradéktétel alapján az
x≡x1modp1α1,x≡x2modp2α2,...,x≡xrmodprαr
kongruencia-rendszernek van egy x megoldása. Erre az x-re P(x) osztható lesz piαi-vel minden 1≤i≤r-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.