Magasabb fokú kongruenciák
Legyen m>0 adott, egész együtthatós polinom. Ekkor tekinthetjük az egyismeretlenes kongruenciát, melynek megoldásait modulo m keressük, azaz azon maradékosztályokat, amelyek kielégítik a kongruenciát. Akárcsak a lineáris kongruenciáknál, a megoldásszámon itt is 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