Magasabb fokú kongruenciák

Legyen m>0 adott, ${\displaystyle f(x)=a_{0}+a_{1}x+\dots a_{k}x^{k}}$ egész együtthatós polinom. Ekkor tekinthetjük az ${\displaystyle f(x)\equiv 0{\pmod {m}}}$ 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.

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 ${\displaystyle f(x)=a_{0}+a_{1}x+\dots a_{n}x^{n}}$ polinom modulo m vett fokszáma k, ha ${\displaystyle a_{k}\not \equiv 0{\pmod {m}}}$, de minden i>k esetén ${\displaystyle a_{i}\equiv 0{\pmod {m}}}$. 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.

Ha p prím és az f polinom modulo p vett foka k, akkor az ${\displaystyle f(x)\equiv 0{\pmod {p}}}$ kongruencia megoldásszáma legfeljebb k.
Megjegyzés: Összetett modulusra a tétel állítása nem igaz.

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 ${\displaystyle c\in \mathbb {Z} }$ egészre ${\displaystyle f(c)\equiv g(c){\pmod {p}}}$.
Megjegyzés: A tételből következik, hogy ${\displaystyle f(x)\equiv 0{\pmod {p}}}$ és ${\displaystyle g(x)\equiv 0{\pmod {p}}}$ kongruenciáknak ugyanazok a megoldásai.
Bizonyítás:
Az f polinomban ${\displaystyle x^{p}}$ 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 ${\displaystyle c\in \mathbb {Z} }$ egészre ${\displaystyle c^{p}\equiv c{\pmod {p}}}$, ezért az ${\displaystyle f(c)\equiv g(c){\pmod {p}}}$ 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.

Legyen ${\displaystyle \ (a,m)=1}$. A legkisebb olyan ${\displaystyle k\in \mathbb {Z} ^{+}}$ számot, melyre ${\displaystyle a^{k}\equiv 1{\pmod {m}}}$, az a rendjének nevezzük modulo m.
Jelölése: ${\displaystyle \ o_{m}(a)}$.
Megjegyzés: Az Euler${\displaystyle -}$Fermat-tételből következik, hogy minden ${\displaystyle \ (a,m)=1}$ esetén létezik az a-nak rendje és ${\displaystyle o_{m}(a)\leq \varphi (m)}$. Ha ${\displaystyle (a,m)\neq 1}$, akkor a-nak nem létezik ilyen szám.

A legfontosabb tételek:
Legyenek ${\displaystyle m>0,(a,m)=1}$ továbbá ${\displaystyle t,u,v\in \mathbb {Z} ^{+}}$. Ekkor:

• ${\displaystyle a^{t}\equiv 1{\pmod {m}}\Leftrightarrow o_{m}(a)\mid t}$.
• ${\displaystyle a^{u}\equiv a^{v}{\pmod {m}}\Leftrightarrow u\equiv v{\pmod {o_{m}(a)}}}$.
• a-nak ${\displaystyle o_{m}(a)}$ db páronként inkongruens hatványa van.
• ${\displaystyle o_{m}(a)\mid \varphi (m)}$.

Lásd még: multiplikatív rend

Egy g számot primitív gyöknek nevezünk modulo m, ha ${\displaystyle o_{m}(g)=\varphi (m)}$, azaz ha a g rendje a nála kisebb, m-hez relatív prímek száma (Euler-féle ${\displaystyle \varphi }$ függvény).

A legfontosabb tételek:

• Egy g szám akkor és csak akkor primitív gyök modulo m, ha ${\displaystyle 1,g,\dots ,g^{\varphi (m)-1}}$ 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:
• ${\displaystyle \ m=2}$
• ${\displaystyle \ m=4}$
• ${\displaystyle \ m=p^{\alpha }}$
• ${\displaystyle \ m=2p^{\alpha }}$

ahol p>2 prím és ${\displaystyle \alpha }$>0.
Megjegyzés: Prím modulus esetén a páronként inkongruens primitív gyökök száma ${\displaystyle \varphi (p-1)}$.
Lásd még: primitív gyök

Legyen p prím, g primitív gyök modulo p és ${\displaystyle (a,p)=1}$. Ekkor az a-nak a g alapú indexén azt a ${\displaystyle 0\leq k\leq p-2}$ számot értjük, melyre ${\displaystyle a\equiv g^{k}{\pmod {p}}}$.
Jelölés: ${\displaystyle \ ind_{g,p}(a)}$ (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:

• ${\displaystyle a\equiv b{\pmod {p}}\Rightarrow ind_{g,p}(a)=ind_{g,p}(b)}$
• ${\displaystyle g^{s}\equiv g^{t}{\pmod {p}}\Leftrightarrow s\equiv t{\pmod {p-1}}}$ (ez következik a rendnél felsorolt tételek közül a másodikból megfelelő szereposztással).
  • ${\displaystyle g^{j}\equiv a{\pmod {p}}\Leftrightarrow g^{j}\equiv g^{ind_{g,p}(a)}{\pmod {p}}\Leftrightarrow j\equiv ind_{g,p}(a){\pmod {p-1}}}$

Megjegyzések:

• Az indexre is érvényesek a logaritmusazonosságok. Például: ha (ab,p)=1, akkor ${\displaystyle \ ind_{g,p}(ab)=ind_{g,p}(a)+ind_{g,p}(b)}$.
• 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.

A pozitív számok körében vett gyökvonáshoz használatos módszert alkalmazhatjuk modulo p gyökvonáshoz, azaz a ${\displaystyle x^{k}\equiv a{\pmod {p}}}$ 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 ${\displaystyle cx^{k}\equiv d{\pmod {p}}}$, ahol ${\displaystyle c\not \equiv 0{\pmod {p}}}$ a fent említett alakra hozható. A megfelelő a értéket a ${\displaystyle cy\equiv d{\pmod {p}}}$ lineáris kongruencia megoldása adja (ez egyetlen maradékosztály, hiszen p prím, ezért a (c,p)=1).
• Ha ${\displaystyle (a,p)\neq 1}$, akkor ${\displaystyle a\equiv 0{\pmod {p}}}$, azaz ${\displaystyle x^{k}\equiv 0{\pmod {p}}}$ kongruenciát kapjuk, aminek csak az ${\displaystyle x\equiv 0{\pmod {p}}}$ az egyetlen megoldása.

Legyen p prím és ${\displaystyle (a,p)=1}$. Az ${\displaystyle x^{k}\equiv a{\pmod {p}}}$ kongruencia akkor és csak akkor megoldható, ha ${\displaystyle a^{\frac {p-1}{(k,p-1)}}\equiv 1{\pmod {p}}}$. Ez a feltétel ekvivalens azzal, hogy ${\displaystyle (k,p-1)\mid ind_{g,p}(a)}$, ahol g egy tetszőleges primitív gyök modulo p.
Ha a kongruencia megoldható, akkor a megoldások száma ${\displaystyle (k,p-1)}$.
Bizonyítás:
A megoldást g primitív gyök szerinti indexet használva a következő alakban keressük: ${\displaystyle x\equiv \ g^{ind(x)}{\pmod {p}}}$.
Ekkora a kongruencia felírható a következő alakban: ${\displaystyle g^{k\;ind(x)}\equiv g^{ind(a)}{\pmod {p}}}$. A rendnél említett ${\displaystyle g^{u}\equiv g^{v}{\pmod {p}}\Leftrightarrow u\equiv v{\pmod {p-1)}}}$ tétel alapján a kongruencia tovább ekvivalens: ${\displaystyle k\;ind(x)\equiv ind(a){\pmod {p-1}}}$ kongruenciával.
Ez ${\displaystyle ind(x)}$-re nézve lineáris, amely akkor és csak akkor oldható meg, ha ${\displaystyle (k,p-1)\mid ind_{g,p}(a)}$, azaz ezen állítás az eredeti kongruencia megoldhatóságának szükséges és elégséges feltétele.

A ${\displaystyle k\;ind(x)\equiv ind(a){\pmod {p-1}}}$ kongruenciának (az eredeti kongruenciával egyetemben) ${\displaystyle (k,p-1)}$ 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:

${\displaystyle a^{\frac {p-1}{(k,p-1)}}\equiv \left(g^{ind(a)}\right)^{\frac {p-1}{(k,p-1)}}=g^{(p-1){\frac {ind(a)}{(k,p-1)}}}{\pmod {p}}}$. 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 ${\displaystyle (k,p-1)\mid ind(a)}$.

Prímmodulusú, magasabb fokú kongruenciákra vonatkozó két nevezetes tétel: Chevalley-tétel, Kőnig–Rados-tétel.

• Freud─Gyarmati: Számélmélet, Nemzeti Tankönyvkiadó, 2000