Kongruencia

A kongruencia a számelméletben az oszthatósági kérdéseket, a maradékokkal való számolást radikálisan leegyszerűsítő jelölésmód.

A kongruencia egy reláció, amelyet az egész számok halmazán értelmezünk. Egy ilyen reláció kifejezi, hogy két szám adott számmal vett osztási maradéka egyenlő-e. Ezen relációkon és azok között végezhetünk műveleteket (összeadás, kivonás, szorzás, osztás, hatványozás – elvégzésükhöz különböző feltételeknek kell teljesülni, ezeket lásd lejjebb). Azonban ennél komolyabb dolgokra is használatos, amire példa a maradékosztályok vagy Chevalley tétele.

Ha két egész szám nem kongruens, akkor inkongruensnek nevezik őket.

Definíció

Legyen $a,b$ tetszőleges egész szám, $m$ zérótól különböző természetes szám.

Azt mondjuk, hogy a kongruens b-vel modulo m, azaz hogy a és b egészek m-mel vett osztási maradéka egyenlő, ha

$m\mid a-b$

azaz

$\mathrm{\exists }k\in \mathbb{Z}:a=km+b$

Jelölése: $a\equiv b(\mathrm{mod}m)$ vagy $a\equiv b(m)$.

Lehet találkozni a következő jelölésekkel is:

• $a\equiv bmodm$
• $a\equiv bmodm\mathbb{Z}$
• $a{\equiv }_{m}b$

Ha a nem kongruens b-vel modulo m, azt mondjuk, inkongruens vele, és $a\equiv ̸b(\mathrm{mod}m)$ vagy $a\equiv ̸b(m)$ alakban jelöljük.

Az itt szereplő $\mathrm{mod}$ a matematikai maradékképző függvény, ami a maradékos osztás maradékát rendeli a számhoz.

Példák

Az 5 kongruens 11-gyel modulo 3, mert $5:3=1\text{ maradék }2$, és $11:3=3\text{ maradék }2$. A két maradék megegyezik, mivel $11-5=6=2\cdot 3$.

Az 5 inkongruens 11-gyel modulo 4, mivel $5:4=1\text{ maradéka }1$ és $11:4=2\text{ maradék }3$; a maradékok nem egyeznek.

A −8 kongruens 10-zel modulo 6, hiszen a 6-tal vett osztási maradék mindkét esetben 4. Valóban, $-8=(-2)\cdot 6+4$.

Története

A kongruenciák ma is használatos elméletét 1801-ben Carl Friedrich Gauss dolgozta ki Disquisitiones Arithmeticae című művében. Magát a fogalmat már Christian Goldbach 1730-ban Leonhard Euler-nek írt levelében is használta, azonban korántsem olyan mélységben, mint Gauss. Goldbach a $\equiv$ szimbólum helyett a $\mp$ jelet használta.

Sőt, már Ch'in Chiu-Shao kínai matematikus is ismerte a fogalmat, amivel kapcsolatos elméletét az 1247-ben írt Matematikai értekezés kilenc fejezetben című művében le is írt. Ebben szerepelt a kínai maradéktétel egy formája is.

Elemi tulajdonságai

A kongruencia ekvivalenciareláció, azaz reflexív, szimmetrikus és tranzitív: tetszőleges $a,b,c\in \mathbb{Z}$, valamint $m\in {\mathbb{Z}}^{+}$ esetén

• $a\equiv a(\mathrm{mod}m)$
• $a\equiv b(\mathrm{mod}m)\Rightarrow b\equiv a(\mathrm{mod}m)$
• $a\equiv b(\mathrm{mod}m),b\equiv c(\mathrm{mod}m)\Rightarrow a\equiv c(\mathrm{mod}m)$

Az ekvivalenciaosztályokat maradékosztályoknak nevezzük. Az elnevezés arra utal, hogy megfeleltethetőek az m-mel való osztás lehetséges maradékainak.

A kongruenciára kimondható számos, az egyenlőségre érvényes azonosság megfelelője: kongruens számok összege és szorzata is kongruens. Legyen $a,b,c,d\in \mathbb{Z}$ és $m,n\in {\mathbb{Z}}^{+}$. Ekkor

• $a\equiv b(\mathrm{mod}m),c\equiv d(\mathrm{mod}m)\Rightarrow a+c\equiv b+d(\mathrm{mod}m)$
• $a\equiv b(\mathrm{mod}m),c\equiv d(\mathrm{mod}m)\Rightarrow a-c\equiv b-d(\mathrm{mod}m)$
• $a\equiv b(\mathrm{mod}m),c\equiv d(\mathrm{mod}m)\Rightarrow ac\equiv bd(\mathrm{mod}m)$

Az egyenlőség a kongruencia speciális esetének is tekinthető:

$a\equiv b(\mathrm{mod}0)\Rightarrow a=b$.

Ha $f\in \mathbb{Z}[X]$ polinom az egész számok fölött, akkor

$f(a)\equiv f(a^{\prime })(\mathrm{mod}m)$

Kongruencia osztása egész számmal

Az osztásnál már nem olyan egyszerű a helyzet, mint az egyenleteknél, ugyanis ha a szám amivel osztani szeretnénk nem relatív prím a modulussal, akkor a modulust is osztani kell.
Legyen $d=(c,m)$ a c és m egészek legnagyobb közös osztója. Ekkor $ac\equiv bc(\mathrm{mod}m)\iff a\equiv b(\mathrm{mod}\frac{m}{d})$.

Ennek az állításnak megnézzük a bizonyítását is, a többi állításé is hasonlóan történik.

Definíció alapján: $ac\equiv bc(\mathrm{mod}m)\iff m\mid (a-b)c$, ami ekvivalens a $\frac{m}{d}\mid (a-b)\frac{c}{d}$ oszthatósággal.
Mivel $(\frac{m}{d},\frac{c}{d})=1$, ezért a fenti oszthatóság pontosan akkor teljesül, ha $\frac{m}{d}\mid a-b$, ami a kongruencia definíciója alapján épp az állítás.

Megjegyzés: a tétel következménye, hogy $ac\equiv bc(\mathrm{mod}m),(c,m)=1\Rightarrow a\equiv b(\mathrm{mod}m)$.

Ez azt is jelenti, hogy, ha $d$ osztója $m$-nek, akkor $a\equiv b(\mathrm{mod}m)$ esetén $a\equiv b(\mathrm{mod}d)$.

Fontos megemlítenünk a következő két tételt, ugyanis a kongruenciákkal kapcsolatban nagyon gyakran felmerülnek, és nagy segítséget nyújtanak bizonyos feladatok, tételek megoldásában.

Euler–Fermat-tétel

Sablon:Bővebben A tétel a moduláris számelmélet egyik legfontosabb állítása, nagyon sok komolyabb tétel bizonyításánál felhasználható, és ami által azok bizonyítása is lényegesen leegyszerűsödik.
A tétel állítása:

$a,m\in \mathbb{Z},m>1,(a,m)=1\Rightarrow a^{\phi (m)}\equiv 1(\mathrm{mod}m)$

A kis Fermat-tétel

Sablon:Bővebben A tétel az Euler-Fermat-tétel egy speciális esete, mely időben korábban fogalmazódott meg, és a bizonyítása egy évszázaddal megelőzte az általános esetet. Itt a modulus prím, ekkor a $\phi (p)=p-1$ miatt a következő állítást kapjuk:

Ha $a$ egész szám, $p$ olyan prím, ami nem osztja $a$-t, akkor $a^{p-1}\equiv 1(\mathrm{mod}p)$.

A tétel egy másik, gyakori alakja:

Ha $a$ egész szám, $p$ prím, akkor $a^p\equiv a(\mathrm{mod}p)$.

Kínai maradéktétel

A kínai maradéktétel szerint: Ha $m_1,m_2,\dots ,m_k$ nullától különböző egész számok, és $m$ a legkisebb közös többszörösük, akkor:

$a\equiv a^{\prime }(\mathrm{mod}{m}_{\kappa })$ minden $\kappa =1,2,\dots ,k\iff a\equiv a^{\prime }(\mathrm{mod}m)$

Hatványozás

Ha $n\in {\mathbb{N}}_0$ természetes szám, akkor

$a^n\equiv (a^{\prime }{)}^n(\mathrm{mod}m)$

Relatív prím $a$ és $m$ esetén teljesül az Euler-Fermat-tétel:

$a^{\phi (m)}\equiv 1(\mathrm{mod}m)$,

ahol $\phi (m)$ az Euler-féle φ-függvény. Ebből következik $a^n\equiv a^{n^{\prime }}(\mathrm{mod}m)$, hogyha $n\equiv n^{\prime }(\mathrm{mod}\phi (m))$. Ennek speciális esete a kis Fermat-tétel.

Példák

• Ha $t\ne 0$, akkor $t\cdot a\equiv t\cdot b(\mathrm{mod}|t|\cdot m)$.
• Ha $a$ páratlan, akkor $a^2\equiv 1(\mathrm{mod}8)$.
• Minden egész számra teljesül a következők valamelyike:

$a^3\equiv 0(\mathrm{mod}9)$ vagy $a^3\equiv 1(\mathrm{mod}9)$ vagy $a^3\equiv 8(\mathrm{mod}9)$.

• Ha $a$, akkor $a^3\equiv a(\mathrm{mod}6)$.
• Minden egész számra teljesül a következők valamelyike:

$a^3\equiv 0(\mathrm{mod}7)$ vagy $a^3\equiv 1(\mathrm{mod}7)$ vagy $a^3\equiv 6(\mathrm{mod}7)$.

• Minden egész számra teljesül a következők valamelyike:

$a^4\equiv 0(\mathrm{mod}5)$ vagy $a^4\equiv 1(\mathrm{mod}5)$.

• Hogyha $a$ teljes hatodik hatvány, azaz négyzet- és köbszám is, akkor $a\equiv 0(\mathrm{mod}36)$ vagy $a\equiv 1(\mathrm{mod}36)$ vagy $a\equiv 9(\mathrm{mod}36)$ vagy $a\equiv 28(\mathrm{mod}36)$.
• Legyen $p$ prímszám úgy, hogy $n<p<2n$. Ekkor $(\genfrac{}{}{0ex}{}{2n}{n})\equiv 0(\mathrm{mod}p)$.
• Legyen $a$ páratlan, $n>0$ pozitív egész szám. Ekkor $a^{2^n}\equiv 1(\mathrm{mod}{2}^{n+2})$.
• Legyen $p>3$, illetve $p$ és $q=p+2$ ikerprímek. Ekkor $p\cdot q\equiv -1(\mathrm{mod}9)$.

A kongruenciaosztályok gyűrűje

A modulo n nullával kongruens számok az egész számok egy ideálját alkotják, az $n\mathbb{Z}$ a más számokkal kongruensek pedig ennek mellékosztályait. Így definiálhatjuk a ${\mathbb{Z}}_n=\mathbb{Z}/n\mathbb{Z}$ faktorcsoportot, amelynek elemei az ${\bar{a}}_n=\{\dots ,a-2n,a-n,a,a+n,a+2n,\dots \}$ maradékosztályok. (Néha az $[a]$ jelölést is használják.) A faktorcsoport a ${\bar{0}}_n,{\bar{1}}_n,{\bar{2}}_n,\dots ,{\overline{n-1}}_n$ elemekből áll, műveletei egyszerűen visszavezethetőek az egész számok műveleteire:

• ${\bar{a}}_n+{\bar{b}}_n={\overline{a+b}}_n$
• ${\bar{a}}_n-{\bar{b}}_n={\overline{a-b}}_n$
• ${\bar{a}}_n{\bar{b}}_n={\overline{ab}}_n$

${\mathbb{Z}}_n$ ezekkel a műveletekkel egy kommutatív gyűrű; ha n prím, akkor (és csak akkor) test.

Algebra

Azt mondjuk, hogy n szám teljes maradékrendszert alkot modulo m, ha páronként inkongruensek, és n=m. A teljes maradékrendszer teljes marad, ha minden eleméhez hozzáadjuk ugyanazt az egész számot, vagy minden elemét megszorozzuk egy, az m modulushoz relatív prím tényezővel.

Egy maradékosztály redukált maradékosztály, ha reprezentánsai relatív prímek a modulushoz. Ha minden redukált maradékosztályt egy szám reprezentál, akkor a reprezentánsok redukált maradékrendszert alkotnak. Számuk éppen az m modulusnál kisebb, m-hez relatív prímek száma (Euler-féle $\phi$ függvény).

Adott m modulus esetén a redukált maradékrendszer maradékosztályai csoportot alkotnak a szorzásra, de az összeadásra nem. Például, ha m kettőhatvány, akkor a redukált maradékrendszer éppen a páratlan maradékosztályokból fog állni. A modulo m összes maradékosztály csoportot alkot az összeadásra, de a szorzásra általában nem; a maradékosztályok gyűrűje nem nullosztómentes. Például modulo 6 a 2 és a 3 maradékosztályának szorzata a 6 maradékosztálya, ami éppen a 0 maradékosztály. Ez prím modulusra nem fordulhat elő; prím modulussal nincsenek nullosztók, és minden nem nulla maradékosztálynak van inverze. Ha a modulus prím, akkor a maradékosztályok testet alkotnak.

Rend

Sablon:Bővebben Legyen $(a,m)=1$. A legkisebb olyan $k\in {\mathbb{Z}}^{+}$ számot, melyre $a^k\equiv 1(\mathrm{mod}m)$, az a (multiplikatív) 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.

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).

Primitív gyök létezik, ha a modulus prím, kettőhatvány, prímnégyzet, vagy egy prímszám kétszerese.

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ó.)

Lineáris kongruenciák

$ax\equiv b(\mathrm{mod}m)a,b\in \mathbb{Z},m\in {\mathbb{Z}}^{+}$

Ezen kongruenciák megoldásakor azokat az egészeket keressük, ami egy bizonyos számmal (modulus) osztva meghatározott maradékot ad. Ezek a diofantoszi egyenletek megfelelői, mindössze más alakban írjuk fel. A megoldásokat maradékosztályokként keressük, és a megoldásszámon a megoldó maradékosztályok számát értjük. Ez a lineáris kongruencia akkor oldható meg, ha $g=\mathrm{lnko}(a,m)$ a $b$ számnak is osztója. Ekkor $g$-vel lehet egyszerűsíteni, és modulo $\frac{m}{g}$ megoldani a kongruenciát. Visszahelyettesítve a megoldást az eredeti kongruenciába, $g$ megoldást találunk.

A megoldást kibővített euklideszi algoritmussal megtalálhatjuk, ahonnan kapjuk az $s$, $t$ egészeket úgy, hogy:

$g=\mathrm{lnko}(a,m)=s\cdot a+t\cdot m$

Innen egy megoldás kapható, mint:

$x_1=\frac{s\cdot c}{g}$,

a többi pedig ettől $\frac{m}{g}$-szeresben különbözik.

Például $4x\equiv 10(\mathrm{mod}18)$ megoldható, hiszen $\mathrm{lnko}(4,18)=2$ osztója a $10$-nek is, és a megoldásszám $2$. A kibővített euklideszi algoritmus eredménye $2=-4\cdot 4+1\cdot 18$, amiből adódik az $x_1=\frac{-4\cdot 10}{2}=-20$ megoldás. A megoldások egy maradékosztályt alkotnak modulo $\frac{18}{2}=9$, így a megoldáshalmaz $\{\cdots ,-20,-11,-2,7,16,25,\cdots \}$.

Magasabb fokú kongruenciák

Sablon:Bővebben 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.

Ezen kongruenciákat hasonlíthatjuk a magasabb fokú egyenletekhez. Ezek megoldása bizonyos esetekben nagyon leegyszerűsíthető, de nincsenek megoldóképletek, csak algoritmusok, amelyek elvezetnek a kívánt eredményhez.

Szimultán kongruenciák

Egy

$a_{1}x\equiv c_1(\mathrm{mod}{m}_1)$

$a_{2}x\equiv c_2(\mathrm{mod}{m}_2)$

$a_{3}x\equiv c_3(\mathrm{mod}{m}_3)$

alakú szimultán kongruencia megoldható, ha:

• minden $i$-re $c_i$ osztható $g_i=\mathrm{lnko}(a_i,m_i)$-vel, azaz minden kongruencia egyenként megoldható,
• és minden $\frac{m_i}{g_i}$ relatív prím.

A kínai maradéktétel bizonyítása megoldási módszert ad a szimultán kongruenciákra.

Kapcsolat a modulo függvénnyel

Ha $a,b,m\in \mathbb{Z}$, $m\ne 0$, akkor:

$a\equiv b(\mathrm{mod}m)\iff (amodm)=(bmodm)\iff (a-b)modm=0$

Programozáskor ügyelni kell arra, hogy több programozási nyelv a matematikaitól eltérően definiálja a maradékot negatív számokra. A szimmetrikus maradékképzés helyett az

$(amodm):=a-\lfloor \frac{a}{m}\rfloor \cdot m$

matematikai modulo függvényt kell alkalmazni, melynek előjele $m$ előjelétől függ. Ezzel a definícióval $(-1)mod7=6$, és az azonos maradékosztályba tartozó számok ugyanazt a maradékot adják ugyanarra a modulusra.

Alkalmazások

A következőkben a kongruenciák néhány alkalmazása következik.

• A nehezebb (nagyon nagy számok, hatványok) maradékos osztások kongruenciává alakítása során könnyebb kiszámolni az eredményt (az ismert tételek segítségével).
• Számos egyszerű ellenőrző összeg, például a személyi azonosítókban, bankkártyákban használt Luhn-formula egyszerű lineáris kongruenciaként számítható ki.
• A lineáriskongruencia-generátor az egyik széles körben elterjedt pszeudorandom generátor.
• A kriptográfiában egyes nyílt kulcsú titkosítások, például az RSA-eljárás és a Diffie–Hellman alapjául szolgál. Számos szimmetrikus kulcsú rejtjelezés is használja, például az AES, az IDEA vagy az RC4.
• A prímtesztelések (Pepin-teszt, Rabin–Miller-teszt, Fermat-teszt) bizonyos kongruenciák vizsgálatát követelik.

Források

• Freud–Gyarmati: Számelmélet, Nemzeti Tankönyvkiadó, 2000
• Christian Spannagel: Kongruenzen und Restklassen. Vorlesungsreihe, 2012.