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{\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.

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}\not \equiv 0{\pmod {m}}$, de minden i>k esetén $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.

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{\pmod {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){\pmod {p}}$.
Megjegyzés: A tételből következik, hogy $f(x)\equiv 0{\pmod {p}}$ és $g(x)\equiv 0{\pmod {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{\pmod {p}}$, ezért az $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.

Rend

Legyen $\ (a,m)=1$. A legkisebb olyan $k\in \mathbb {Z} ^{+}$ számot, melyre $a^{k}\equiv 1{\pmod {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)\leq \varphi (m)$. Ha $(a,m)\neq 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{\pmod {m}}\Leftrightarrow o_{m}(a)\mid t$.
• $a^{u}\equiv a^{v}{\pmod {m}}\Leftrightarrow u\equiv v{\pmod {o_{m}(a)}}$.
• a-nak $o_{m}(a)$ db páronként inkongruens hatványa van.
• $o_{m}(a)\mid \varphi (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)=\varphi (m)$, azaz ha a g rendje a nála kisebb, m-hez relatív prímek száma (Euler-féle $\varphi$ 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^{\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:
• $\ 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 $\varphi (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\leq k\leq p-2$ számot értjük, melyre $a\equiv g^{k}{\pmod {p}}$.
Jelölés: $\ 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:

• $a\equiv b{\pmod {p}}\Rightarrow ind_{g,p}(a)=ind_{g,p}(b)$
• $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).
  • $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 $\ 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.

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{\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 $cx^{k}\equiv d{\pmod {p}}$, ahol $c\not \equiv 0{\pmod {p}}$ a fent említett alakra hozható. A megfelelő a értéket a $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 $(a,p)\neq 1$, akkor $a\equiv 0{\pmod {p}}$, azaz $x^{k}\equiv 0{\pmod {p}}$ kongruenciát kapjuk, aminek csak az $x\equiv 0{\pmod {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{\pmod {p}}$ kongruencia akkor és csak akkor megoldható, ha $a^{\frac {p-1}{(k,p-1)}}\equiv 1{\pmod {p}}$. Ez a feltétel ekvivalens azzal, hogy $(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 $(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)}{\pmod {p}}$.
Ekkora a kongruencia felírható a következő alakban: $g^{k\;ind(x)}\equiv g^{ind(a)}{\pmod {p}}$. A rendnél említett $g^{u}\equiv g^{v}{\pmod {p}}\Leftrightarrow u\equiv v{\pmod {p-1)}}$ tétel alapján a kongruencia tovább ekvivalens: $k\;ind(x)\equiv ind(a){\pmod {p-1}}$ kongruenciával.
Ez $ind(x)$-re nézve lineáris, amely akkor és csak akkor oldható meg, ha $(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 $k\;ind(x)\equiv ind(a){\pmod {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)}}}{\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 $(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