Magasabb fokú kongruenciák

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

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

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

Rend

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

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

• $a^t\equiv 1(\mathrm{mod}m)\iff o_m(a)\mid t$.
• $a^u\equiv a^v(\mathrm{mod}m)\iff u\equiv v(\mathrm{mod}{o}_m(a))$.
• a-nak $o_m(a)$ db páronként inkongruens hatványa van.
• $o_m(a)\mid \phi (m)$.

Lásd még: multiplikatív rend

Primitív gyök

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

A legfontosabb tételek:

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

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

Index (diszkrét logaritmus)

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

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

Megjegyzések:

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

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 $x^k\equiv a(\mathrm{mod}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 $c{x}^k\equiv d(\mathrm{mod}p)$, ahol $c\equiv ̸0(\mathrm{mod}p)$ a fent említett alakra hozható. A megfelelő a értéket a $cy\equiv d(\mathrm{mod}p)$ lineáris kongruencia megoldása adja (ez egyetlen maradékosztály, hiszen p prím, ezért a (c,p)=1).
• Ha $(a,p)\ne 1$, akkor $a\equiv 0(\mathrm{mod}p)$, azaz $x^k\equiv 0(\mathrm{mod}p)$ kongruenciát kapjuk, aminek csak az $x\equiv 0(\mathrm{mod}p)$ az egyetlen megoldása.

Tétel (Megoldhatóság, megoldások száma, megoldási algoritmus)

Legyen p prím és $(a,p)=1$. Az $x^k\equiv a(\mathrm{mod}p)$ kongruencia akkor és csak akkor megoldható, ha $a^{\frac{p-1}{(k,p-1)}}\equiv 1(\mathrm{mod}p)$. Ez a feltétel ekvivalens azzal, hogy $(k,p-1)\mid in{d}_{g,p}(a)$, ahol g egy tetszőleges primitív gyök modulo p.
Ha a kongruencia megoldható, akkor a megoldások száma $(k,p-1)$.
Bizonyítás:
A megoldást g primitív gyök szerinti indexet használva a következő alakban keressük: $x\equiv g^{ind(x)}(\mathrm{mod}p)$.
Ekkora a kongruencia felírható a következő alakban: $g^{kind(x)}\equiv g^{ind(a)}(\mathrm{mod}p)$. A rendnél említett $g^u\equiv g^v(\mathrm{mod}p)\iff u\equiv v(\mathrm{mod}p-1))$ tétel alapján a kongruencia tovább ekvivalens: $kind(x)\equiv ind(a)(\mathrm{mod}p-1)$ kongruenciával.
Ez $ind(x)$-re nézve lineáris, amely akkor és csak akkor oldható meg, ha $(k,p-1)\mid in{d}_{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 $kind(x)\equiv ind(a)(\mathrm{mod}p-1)$ kongruenciának (az eredeti kongruenciával egyetemben) $(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:

$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)}}(\mathrm{mod}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 $(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.

Források

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