A magasabb fokú kongruenciák a számelméletben olyan kongruenciák, amiket egy egynél magasabb fokszámú egész együtthatós polinom definiál. Ezzel szemben a lineáris kongruenciákat definiáló polinomok elsőfokúak.
Definíció Legyen m egy pozitív egész szám, és legyen egy egész együtthatós polinom. Ekkor tekinthetjük az egyismeretlenes kongruenciát, melynek megoldásait modulo m keressük. Másképp fogalmazva azon moduló m maradékosztályokat keressük, amelyek kielégítik a kongruenciát. Ez a definíció értelmes: valóban, könnyen ellenőrizhető, hogy ha az x egész szám megoldása a kongruenciának, akkor is az tetszőleges i egész számra.
Ha , akkor lineáris kongruenciáról beszélünk. Egy kongruencia megoldásszámán a megoldó maradékosztályok számát értjük.
Fokszám A polinomoknál definiált fokszámot értelmezhetjük ezeknél a kongruenciáknál is modulo m, méghozzá a következőképpen: Az polinom modulo m vett fokszáma k, ha , de minden i>k esetén . Ha a polinom minden együtthatója 0-val kongruens modulo m, akkor f-nek nincs foka modulo m.
A következő két tétel prím modulusú kongruenciákra vonatkoznak.
Tétel (Megoldások száma prím modulusú kongruenciák esetén) Ha p prím és az f polinom modulo p vett foka k, akkor az kongruencia megoldásszáma legfeljebb k. Megjegyzés: Összetett modulusra a tétel állítása nem igaz.
Tétel (Redukció prím modulusú kongruenciák esetén) Ha p prím és f egész együtthatós polinom, akkor létezik (egyetlen) olyan g egész együtthatós polinom, melynek modulo p vett foka legfeljebb p-1 (vagy nem létezik foka – azaz az összes együttható 0) és minden egészre . Megjegyzés: A tételből következik, hogy és kongruenciáknak ugyanazok a megoldásai. Bizonyítás: Az f polinomban helyére mindenhol írjunk x-et, amíg lehetséges. Ekkor egy olyan polinomot kapunk, amelynek modulo p vett foka legfeljebb p-1 (vagy minden együttható 0). Mivel p prím, ezért a kis Fermat-tétel szerint bármely egészre , ezért az teljesül.
A következő fogalmak bevezetésére a magasabb fokú kongruenciák vizsgálatakor betöltött kiemelt szerepük miatt van szükség.
Rend Legyen . A legkisebb olyan számot, melyre , az a rendjének nevezzük modulo m. Jelölése: . Megjegyzés: Az EulerFermat-tételből következik, hogy minden esetén létezik az a-nak rendje és . Ha , akkor a-nak nem létezik ilyen szám.
A legfontosabb tételek: Legyenek továbbá . Ekkor: . . a-nak db páronként inkongruens hatványa van. . Lásd még: multiplikatív rend
Primitív gyök Egy g számot primitív gyöknek nevezünk modulo m, ha , azaz ha a g rendje a nála kisebb, m-hez relatív prímek száma (Euler-féle függvény).
A legfontosabb tételek: Egy g szám akkor és csak akkor primitív gyök modulo m, ha redukált maradékredszert alkotnak modulo m. Az m>1 modulusra nézve akkor és csak akkor létezik primitív gyök, ha m a következők egyike:
ahol p>2 prím és >0. Megjegyzés: Prím modulus esetén a páronként inkongruens primitív gyökök száma . Lásd még: primitív gyök
Index (diszkrét logaritmus) Legyen p prím, g primitív gyök modulo p és . Ekkor az a-nak a g alapú indexén azt a számot értjük, melyre . Jelölés: (Ha a g primitív gyök vagy a p prím egyértelmű adott feladatnál, akkor a jelölésből elhagyható.)
A legfontosabb tételek:
(ez következik a rendnél felsorolt tételek közül a másodikból megfelelő szereposztással).
Megjegyzések: Az indexre is érvényesek a logaritmusazonosságok. Például: ha (ab,p)=1, akkor . A diszkrét logaritmus számítása használatos a kriptográfiában, ugyanis ha p nagy prím, a pedig p-nél kisebb pozitív egész, akkor az index számítása nem könnyű.
A továbbiakban magasabb fokú kongruenciák egy speciális esetével foglalkozunk, ahol a prímmodulusból és az alakból a megoldás lényegesen leegyszerűsödik.
Binom kongruenciák A pozitív számok körében vett gyökvonáshoz használatos módszert alkalmazhatjuk modulo p gyökvonáshoz, azaz a kongruencia megoldásához, ahol p prím. Az ilyen alakú kongruenciákat binom (kéttagú) kongruenciáknak nevezzük. Megjegyzés: Az általános alak , ahol a fent említett alakra hozható. A megfelelő a értéket a lineáris kongruencia megoldása adja (ez egyetlen maradékosztály, hiszen p prím, ezért a (c,p)=1). Ha , akkor , azaz kongruenciát kapjuk, aminek csak az az egyetlen megoldása.
Tétel (Megoldhatóság, megoldások száma, megoldási algoritmus) Legyen p prím és . Az kongruencia akkor és csak akkor megoldható, ha . Ez a feltétel ekvivalens azzal, hogy , ahol g egy tetszőleges primitív gyök modulo p. Ha a kongruencia megoldható, akkor a megoldások száma . Bizonyítás: A megoldást g primitív gyök szerinti indexet használva a következő alakban keressük: . Ekkora a kongruencia felírható a következő alakban: . A rendnél említett tétel alapján a kongruencia tovább ekvivalens: kongruenciával. Ez -re nézve lineáris, amely akkor és csak akkor oldható meg, ha , azaz ezen állítás az eredeti kongruencia megoldhatóságának szükséges és elégséges feltétele.
A kongruenciának (az eredeti kongruenciával egyetemben) megoldása van a lineáris kongruenciák megoldásszámára vonatkozó tétel alapján.
A két feltétel ekvivalenciájának bizonyítása:
. Ez pontosan akkor kongruens 1-gyel modulo p, ha az utolsó tagban a kitevő a p-1-nek egész számú többszöröse, azaz ha .
Prímmodulusú, magasabb fokú kongruenciákra vonatkozó két nevezetes tétel: Chevalley-tétel, Kőnig–Rados-tétel.
Források Freud─Gyarmati: Számélmélet, Nemzeti Tankönyvkiadó, 2000
Kategória:Számelmélet